mojo's Blog

문제 링크 => 15989번: 1, 2, 3 더하기 4 (acmicpc.net) 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개 이상 사용한다는 것을 못봐서 약간의 뇌절을 했던 문제이다. 그럼 규칙성을 발견해보도록 한다. dp_1[x] => x = 1 + ( ) (( ) 안에 1, 2, 3 으로 구성)로 나타낼 때, ( ) 가 나타낼 수 있는 갯수 dp_23[x] => x = 2 + ( ) (..

문제 링크 => 15486번: 퇴사 2 (acmicpc.net) 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net Dynamic Programming 문제이다. 이 문제는 1일 2일 ... N일 접근을 해서 O(N) 만에 해결하도록 해야 한다. 문제에 주어진 Input을 기반으로 설명하고자 한다. 이때 dp[x] 는 x일 일때의 최대 이익을 의미한다. x T[x] P[x] dp[x] 1 3 10 0 2 5 20 0 3 1 10 0 4 1 20 0 5 2 15 0 6 4 40 0 7 ..

문제 링크 => 11060번: 점프 점프 (acmicpc.net) 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 끝지점까지 문제에서 주어진 조건에 맞게 이동할 수 있는 경우 최소로 점프한 횟수를 반환하고 이동할 수 없는 경우 -1 를 반환한다. i 번째에 점프할 수 있는 횟수를 A[i] 라고 할 때, 0 A[i]; cout

문제 링크 => 5904번: Moo 게임 (acmicpc.net) 5904번: Moo 게임 Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다. Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다. m o o m o o o m o o m o o o www.acmicpc.net 재귀를 이용한 분할 정복문제이다. 이 문제는 다음과 같이 Moo 수열을 만들 수 있다. S(0) = moo S(1) = moo mooo moo S(2) = moo mooo moo moooo moo mooo moo ... S(k) = S(k - 1) moo ... o S(k - 1) (o의 개수는 (k + 2) 개) 이런식으로 Moo 수열을 구할 수 있다. 근데 ..

문제 링크 => 2737번: 연속 합 (acmicpc.net) 2737번: 연속 합 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 정수 하나로 이루어져 있다. 이 정수는 문제에서 설명한 N이며, 231보다 작다. www.acmicpc.net 알고리즘이 수학으로 분류되었지만 binary search 를 이용하여 해결했다. 문제는 굉장히 간단하다. 숫자 N 에 대하여 2개 이상의 연속하는 수의 합이 나올 수 있는 모든 경우의 수를 구하는 문제이다. 간단하게 생각해본다. 임의의 수 (x > 0) 에 대하여 다음과 같은 작업을 계속 해준다. (1) 연속하는 수 2개 ) x + (x + 1) = N 를 만족하는 x 가 있으면 경우의 수를 counting 한다. (2) 연속하는 수 3개 ) x..

문제 링크 => 1515번: 수 이어 쓰기 (acmicpc.net) 1515번: 수 이어 쓰기 세준이는 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 그리고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다. 세준 www.acmicpc.net 문자열을 이용한 구현 문제이다. 먼저 정해진 것은 아니지만 [1, 99999] 범위 내의 모든 숫자을 이어주도록 하는 문자열 s를 설정하였다. 그리고 123456789101112... 이런식으로 나아갈 때 [x, y] 범위 내의 숫자를 z 라고 설정하기 위해 1차원 배열 dp를 둬서 dp[x] = dp[x + 1] = ... = dp[y - 1] = dp[y] = z 이런 식으로 설정하였다. ..