일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
Tags
- kakao
- Movie
- 해설
- 추천
- 코딩 테스트
- BOJ
- 넷플릭스
- coding
- 2020
- Netflix
- Recursive
- 알고리즘
- 영어
- parametric search
- Algorithm
- review
- benefits
- 영화
- health
- 나는솔로
- 백준
- 수능
- BFS
- 카카오
- silver
- 완전탐색
- 리뷰
- Greedy
- usaco
- array
Archives
- Today
- Total
Young
BOJ - 카드 놓기 (5568) 본문
728x90
반응형
https://www.acmicpc.net/problem/5568
5568번: 카드 놓기
문제 상근이는 카드 n(4 ≤ n ≤ 10)장을 바닥에 나란히 놓고 놀고있다. 각 카드에는 1이상 99이하의 정수가 적혀져 있다. 상근이는 이 카드 중에서 k(2 ≤ k ≤ 4)장을 선택하고, 가로로 나란히 정수를 만들기로 했다. 상근이가 만들 수 있는 정수는 모두 몇 가지일까? 예를 들어, 카드가 5장 있고, 카드에 쓰여 있는 수가 1, 2, 3, 13, 21라고 하자. 여기서 3장을 선택해서 정수를 만들려고 한다. 2, 1, 13을 순서대로 나열하면
www.acmicpc.net
전형적인 조합론 문제입니다.
n개 중에서 k개를 뽑는 함수를 만들고, next_permutaion 함수를 사용해 순열을 구합니다.
이때 중복되는 것은 set 으로 처리해주면 됩니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
#include <bits/stdc++.h>
using namespace std;
int n, m;
int k;
vector<int> v, vv;
set<string> st; // 중복처리를 위한 자료구조
void sol(int picked, int limit, int cur) { // picked : 현재 고른 카드의 수, limit : 최대고를 수 있는 카드 수, cur : 현재 고른 카드의 위치
if (picked == limit) { // 모두 골랐으면 이를 처리해주고 return 한다.
do {
string s = "";
for (int i = 0; i < vv.size(); i++) s += to_string(vv[i]);
} while (next_permutation(vv.begin(), vv.end())); // 순열을 통해서 만들 수 있는 숫자를 만들어본다.
return;
}
for (int next = cur + 1; next < v.size(); next++) {
vv.push_back(v[next]);
sol(picked + 1, limit, next);
vv.pop_back();
}
}
int main() {
cin >> n >> k;
v.resize(n);
for (int i = 0; i < n; i++)
cin >> v[i];
sort(v.begin(), v.end()); // next_permutation 을 위해서 미리 정렬을 한 번 해준다.
// 이를 해주지 않으면 모든 순서 조합을 시뮬레이션 해볼 수 없다.
sol(0, k, -1);
cout << st.size();
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs |
728x90
반응형
'코딩 테스트 대비 추천 문제' 카테고리의 다른 글
BOJ - 주사위 윷놀이 (17825) [2019 삼성 SW 기출] (0) | 2019.12.07 |
---|---|
BOJ - 공주님을 구해라! (17836) (0) | 2019.12.03 |
BOJ - 마라톤1 (10655) (0) | 2019.12.03 |
BOJ - 달팽이 리스트 (17827) (0) | 2019.12.03 |
정사각 배열 대각선 순서로 접근 (0) | 2019.04.06 |