완전탐색

문제 : https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 어떤 문제인가? 1부터 짝수인 n까지의 사람이 있다. 팀을 n/2, n/2명으로 두 팀으로 나눈다. 이때, 각 팀원들의 능력치를 합산해서 두 팀의 최종 능력치를 구한다. 그다음, 두 팀의 최종 능력치가 최솟값을 구하면 된다. 접근 방법 팀원들을 나누는 방법은 조합을 사용해서 가능한 모든 경우의 수를 탐색하면 된다. n명 중 n/2명을 뽑으면 나머지 인원들이 다른 팀이 되기 때문이다. int n; int arr..

문제 : https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 어떤 문제인가? 시작 전, 이 문제를 보니 어렸을 때 마인크래프트를 하던 기억이 떠올라 기분이 좋았다. 모든 입력들(땅의 높이)의 값이 같게 만들어야 하고 이때 걸리는 시간과 가장 큰 높이를 출력하면 된다. 접근 방법 int block[500][500]; 먼저 땅이 높이를 저장할 2차원 배열을 선언해줬다. int n, m, b; cin >> n >> m >> b; for (int i =..

문제 : https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 어떤 문제인가? n개의 숫자와 n-1개의 연산자를 입력받는다. 그렇게 되면 만들 수 있는 식이 여러 개 생기게 된다. 이때 모든 식을 계산했을 때의 최댓값과 최솟값을 출력하면 된다. 특이한 점은 식을 계산할 때 연산자의 우선순위를 고려하지 않고 식의 앞쪽부터 차례대로 계산하는 것이다. 접근 방법 vector num; vector op..

문제 : https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 > n; if (n == 0) { break; } vector arr; vector comb(6); for (int i = 0; i > a; arr.push_back(a); } combination(a..

문제 : https://www.acmicpc.net/problem/16457 16457번: 단풍잎 이야기 첫째 줄에 키의 개수 n, 퀘스트의 개수 m, 퀘스트 당 사용해야 하는 스킬의 수 k가 주어진다. n은 10 이하, k는 n 이하의 양의 정수이며, m은 100 이하의 양의 정수이다. 둘째 줄부터 m개의 줄에는 각각 www.acmicpc.net 어떤 문제인가? m개의 퀘스트가 존재한다. 각 퀘스트는 k개의 스킬을 써서 완료할 수 있다. 1부터 2*n까지의 정수 중 n개를 뽑는다. 이때의 정수가 퀘스트를 완료할 때 필요한 스킬이다. 이때 퀘스트를 가장 많이 완료할 수 있는 경우를 찾으면 된다. 접근 방법 int n, m, k; int quest[101][10]; 문제에서 주어진 변수와 입력된 퀘스트를 ..

문제 : https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 어떤 문제인가? 백 트랙킹의 대표적인 문제로 들었다. N * N 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 물어보는 문제이다. 접근 방법 N이 4일 때 (1, 1)부터 퀸을 놓으면서 진행한다. 퀸은 대각선과 직선을 모두 공격할 수 없으므로 한 줄에 퀸이 놓이면 무조건 다음 줄로 넘어가야 한다. 그래서 두 번째 줄로 이동해서 다음 퀸을 놓을 자리를 찾는다. (2, 1), (2, 2)는 ..