알고리즘

문제 : 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/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 어떤 문제인가? 배열이 있을 때 | A [0] - A [1] | + | A [1] - A [2] | +... + | A [N-2] - A [N-1] |의 값이 최대가 되게 배열을 재배치해야 한다. 배열을 재배치하고 난 후 얻을 수 있는 최댓값을 출력하면 된다. 접근 방법 숫자를 재배치하기 위해서는 어떤 숫자를 어디에 배치해야 할지를 결정해야 한다. 따라서 데이터는 앞, 뒤 삭제 삽입 연산이 간편한 de..

문제 : 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/18429 18429번: 근손실 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 www.acmicpc.net 어떤 문제인가? ㅋㅋㅋ참 웃긴 문제이다. 간단하게 문제를 설명하자면 하루에 운동을 마쳤을 때 중량이 500 이하로 되지 않게 하는 루틴을 짜면 된다. 정확히 루틴을 짜는 것이 아니라 가능한 경우의 수를 구하면 된다. 접근 방법 일단 가능한지 불가능한지를 확인하긴 위해선 루틴의 순서가 필요하다. 이 경우에는 순열을 사용해야 한다. 경우의 수를 모두 측정하기 위해선 모든 루틴을 탐..

문제 : 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)는 ..

문제 : https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 어떤 문제인가? 전화번호 목록에 여러 개의 전화번호가 존재한다. 문제의 예시처럼 선영이에게 전화를 걸기 위해선 911을 눌러야 하지만 911이란 번호가 긴급전화라 전화 버튼을 누르지 않아도 바로 전화가 걸린다. 따라서 선영이에게 전화를 거는 것은 불가능하다. 이러한 전화번호 목록을 일관성이 없다고 문제에서 표현했다. 문제는 어떠한 전화번호 목록이 일관성이 있는지 없..