문제 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 풀이 먼저 타일들을 나열해 보자. N = 1 / 1 N = 2 / 00, 11 N = 3 / 001, 111, 100 N = 4 / 0000, 1100, 0011, 1111, 1001 N = 5 / 00001, 11001, 00111, 11111, 10011, 00100, 11100, 10000 타일의 가짓수는 1, 2, 3, 5, 8개로 증가하며 피보나치 수열의 패턴을 보이고 있다. 따라서 dp[N] = dp[N - 1] + dp[N - 2]의 점화식을 사용하..

문제 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 풀이 이 문제는 Traveling Salesman problem(TSP)라고 불리는 외판원 순회 문제 유형의 가장 기본적인 형태이다. DFS로 풀이하면 된다. 한 도시에서 모든 도시를 방문했을 때, 출발지로 다시 돌아올 수 있다면 총 비용을 현재까지의 최솟값과 비교하여 저장하는 방식이다. 모든 도시를 한 번씩 출발지로 하여 dfs()를 호출하면 된다. 코드 import java.util.* import kotlin..

문제 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 이 문제의 유형은 활동 선택 문제(Activity Selection problem)라고하며 대표적인 그리디 문제이다. 활동 선택 문제란 각 활동의 시작 시간과 종료 시간이 주어졌을 때, 한 사람은 한 번에 하나의 활동만 수행할 수 있다고 가정하며, 한 사람이 최대로 수행할 수 있는 활동의 수를 찾는 것을 목표로 하는 것이다. 선택할 수 있는 활동이 많아지려면, 서로 겹치지 않는 활동에 대해 종료시간 빠른 경우를 선택해야 한다. 따라서 활동들을 종료시간을 기준으로 정렬하고 선택한다. 가장 먼저 종료하는 활동을 선택하고, 두 번째 활동부터 활동의 시작 시간이 마지막으로 ..

문제 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 점화식을 만들기 위해 문제에서 주어진 규칙을 보면, 1. 계단은 한번에 한 계단, 두 계단씩 오를 수 있다. 2. 연속된 3개의 계단을 밟으면 안된다. 이 규칙에서 현재 계단 N을 밟기 위한 방법으로는 N - 2에서 N까지 두 계단 이동한 경우와 N - 3에서 N - 1까지 두 계단 이동하고 N - 1에서 N까지 한 계단 이동한 경우로 2가지만 가능하다. 연속해서 3개의 계단을 밟는 것이 불가능하기 때문에 위의 두 가지 방법이 전부가 된다. 그렇다면 현재 계단에서..

문제 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 문제는 하나의 자연수를 1, 2, 3으로 조합하여 만드는 경우의 수를 구하는 것으로 우선 1, 2, 3을 만드는 경우의 수를 먼저 확인해보자. 1을 만드는 경우의 수는 (1)으로 1개고, 2를 만드는 경우의 수는 (1 + 1), (2)로 2개, 3을 만드는 경우의 수는 (1 + 1 + 1), (1 + 2), (2 + 1), (3)으로 4개다. 1, 2, 3을 조합하여 4를 만드는 방법은 (1 + 3), (2 + 2), (3 + 1)로 나타낼 수 있는데, (1 + 3)은 (1) + (1 + 1 + 1), (1) + (1 + 2), (1) + (2 + ..