CEO

1, 2, 3 더하기 시리즈 1, 2, 3 더하기 1, 2, 3 더하기 2 1, 2, 3 더하기 3 1, 2, 3 더하기 4 1, 2, 3 더하기 5 1, 2, 3 더하기 6 1, 2, 3 더하기 7 1, 2, 3 더하기 8 1, 2, 3 더하기 9 문제 15992번: 1, 2, 3 더하기 7 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. 단, 사용한 수의 개수는 m개 이어야 한다. www.acmicpc.net 문제 풀이 N이라는 수를 1, 2, 3이라는 숫자를 사용하여 구할 때, M개의 숫자를 사용하여서 구할 수 있는 경우의 수를 찾는 문제이다. 문제를 풀기 위해서는 구하고자 하는 수 N과 사용하여야 하는 숫자 M이 있으므로..

1, 2, 3 더하기 시리즈 1, 2, 3 더하기 1, 2, 3 더하기 2 1, 2, 3 더하기 3 1, 2, 3 더하기 4 1, 2, 3 더하기 5 1, 2, 3 더하기 6 1, 2, 3 더하기 7 1, 2, 3 더하기 8 1, 2, 3 더하기 9 문제 15991번: 1, 2, 3 더하기 6 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 1, 2, 3의 합으로 N이라는 숫자를 나타내고자 할 때 수식이 대칭인 경우만 방법의 수로 취급하는 문제이다. 문제를 풀기 위해 N이 증가함에 따라 발생하는 경우의 수를 나열하면 아래와 같다. N은 1인 경우: 1개 `1` N은 2인 경우: 2개 `1 ..

1, 2, 3 더하기 시리즈 1, 2, 3 더하기 1, 2, 3 더하기 2 1, 2, 3 더하기 3 1, 2, 3 더하기 4 1, 2, 3 더하기 5 1, 2, 3 더하기 6 1, 2, 3 더하기 7 1, 2, 3 더하기 8 1, 2, 3 더하기 9 문제 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 기존의 문제와 달리 연속된 숫자를 사용할 수 없다는 조건이 추가된 문제이다. 문제를 풀기 위해서 DP를 2차원 배열로 나누어 생각하면 쉽게 문제를 해결할 수 있다. 예를 들어 1, 2, 3 더하기의 경우 점화식을 `dp[n] = dp[n - 1] + d..

1, 2, 3 더하기 시리즈 1, 2, 3 더하기 1, 2, 3 더하기 2 1, 2, 3 더하기 3 1, 2, 3 더하기 4 1, 2, 3 더하기 5 1, 2, 3 더하기 6 1, 2, 3 더하기 7 1, 2, 3 더하기 8 1, 2, 3 더하기 9 문제 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 문제 풀이 기존의 1, 2, 3 더하기 문제와 다른 점이 있다면 순서가 다른 경우 하나의 경우로 생각한다는 것이다. 이를 구하기 위해서는 DFS로 조..

1, 2, 3 더하기 시리즈 1, 2, 3 더하기 1, 2, 3 더하기 2 1, 2, 3 더하기 3 1, 2, 3 더하기 4 1, 2, 3 더하기 5 1, 2, 3 더하기 6 1, 2, 3 더하기 7 1, 2, 3 더하기 8 1, 2, 3 더하기 9 문제 12101번: 1, 2, 3 더하기 2 n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다. www.acmicpc.net 문제 풀이 1, 2, 3을 활용하여 N을 구할 수 있는 경우의 수 중 K 번째의 수식을 출력하는 문제이다. 문제의 경우 N의 크기가 크지 않기 때문에 DFS로 백트랙킹하여 문제를 쉽게 풀 수 있다. 재귀 호출을 하면서 구한 수의 합이 N보다 크다..

문제 14238번: 출근 기록 스타트링크에는 세명의 직원이 일을 하고 있다. 세 직원의 이름은 강호(A), 준규(B), 수빈(C) 이다. 이 회사의 직원은 특별한 룰을 가지고 있는데, 바로 하루에 한 명만 출근한다는 것이다. 3일간의 www.acmicpc.net 문제 풀이 세 직원 A, B, C가 있다. 회사에는 특별한 룰을 가지고 있어서 하루에 한 명만 출근한다. 각 직원에 따라 출근할 수 있는 규칙이 정해져 있다. A의 경우 매일 출근할 수 있으며, B의 출근한 다음날은 쉬어야 한다. C의 경우 출근한 다음날과 그다음 날 모두 쉬어야 한다는 규칙이 있다. 따라서 dp의 배열을 5차원 배열로 `dp[a][b][c][전전날][전날]`과 같이 기록하여, 중복으로 경우의 수를 탐색하지 않도록 하여야 한다. ..

문제 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 � www.acmicpc.net 문제 풀이 1xN의 미로에는 각 칸에 정수가 적혀있다. 예를 들어 칸에 3이 적혀있다면 현재 위치에서 +1, +2, +3으로 점프할 수 있다. 이때, 최소한으로 점프하여 가장 오른쪽 끝으로 갈 수 있을 경우 점프 횟수를 반환하고 그렇지 않을 경우 -1을 반환하여야 한다. 문제를 풀기 위해서는 BFS를 통해, 현재 위치에서 탐색 가능한 경로를 추가하는 방식을 사용하여 탐색을 진행하면 된다. 만약 BFS로 모든 경우의 수를 탐색하여도 답을 찾지 못..

문제 16936번: 나3곱2 나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다. 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 www.acmicpc.net 문제 풀이 정수 하나를 사용하여 연산을 N-1번 적용한다. 적용할 수 있는 연산은 정수가 3으로 나누어 떨어지는 경우 3으로 나누거나, 2를 곱하는 경우가 있다. 문제에 제시된 조건에 따라 DFS를 통하여 구하면 쉽게 문제를 풀 수 있다. DFS로 푸는 것은 다른 문제에서도 많이 다루었고 `서로소`의 성질을 이용하여 3으로 가장 많이 나누어 떨어지는 수부터 정렬하는 방식을 사용하여 푸는 방법이 있다. 만약, DFS로 풀고자 한다면 DFS의 ..