목록다이나믹 프로그래밍 (63)

1일1알

백준 15989번 1, 2, 3 더하기 4 C++

간단한 dp문제일 줄 알았는데, 중복을 허용하지 않는다는 조건이 있어서 풀이를 생각하는데 시간이 조금 걸렸다. 생각해낸 해결법은 오름차순으로 정렬된 경우만 고려하는 것이다. 2차원 dp테이블을 만들어서 dp[i][j]는 i를 만드는 데 마지막에 사용한 숫자는 j 이라는 정보를 저장해서 문제를 해결하였다. dp[4][1]은 4를 만드는데 마지막에 1이 사용되고, 오름차순으로 정렬된 경우만 고려하므로 3을 만들 때 마지막에 1이 사용된 경우만 가능하다. 그러므로 dp[4][1]=dp[3][1] 이기 때문에 dp[i][1]=dp[i-1][1] 이라는 점화식을 하나 얻을 수 있다. dp[4][2]는 4를 만드는데 마지막에 2가 사용되고, 오름차순으로 정렬된 경우만 고려하기 때문에 2를 만들 때 마지막에 1이 사..
알고리즘 2021. 11. 24. 11:50
백준 9658번 돌 게임 4 C++

완벽하게 게임을 했을 때 : 최선의 선택을 했을 때라고 이해하고 문제를 풀었다. 상근이의 기준에서 동전이 1개일 때 : 1개 가져가면 패배 동전이 2개일 때 : 1개 가져가면 상대방이 1개 가져가서 승리 동전이 3개일 때 : 1->1->1 패배, 3개 가져가도 패배 동전이 4개일 때 : 3개 가져가면 상대방이 1개 가져가서 승리 5개부터는 dp를 이용하여 해결할 수 있다. 동전이 5개 이상인 n 개라면 3가지로 나눠볼 수 있다. 처음 4개를 가져갔다면 n-4개일 때, 처음 3개를 가져갔다면 n-3개일 때, 처음 1개를 가져갔다면 n-1개일 때이다. 이 각각의 경우는 처음에 상근이가 가져가고 창영이의 턴으로 넘어갔기 때문에 동전이 n-k개 있을때(k = 4, 3, 1)의 승패의 반대가 된다.(상근이 기준)..
알고리즘 2021. 11. 22. 11:08
백준 2502번 떡 먹는 호랑이 C++

조금 특이한? dp 문제이다. 우선 점화식을 세울 때 생각한 것은 어떤 날이든 첫째 날과 둘째 날의 떡의 개수로 분해할 수 있다는 것이다. 예를 들어 5번째 날은 3번째 날 + 4번째 날이고, 3번째 날은 1번째 날 + 2번째 날, 4번째 날은 2번째 날 + 3번째 날.. 이런 식으로 밑으로 내려가면서 최종적으론 1번째 날과 2번째 날의 떡의 개수의 조합으로 나타낼 수 있다. 그림으로 나타내면 이런 식으로, 5번째 날은 최종적으로 2 * 1번째 날, 3* 2번째 날의 떡의 개수로 나타낼 수 있다. 하지만 숫자가 주어질 때마다 이런 식으로 계속 분해하면 시간이 오래 걸리기 때문에 bottom-up 방식으로 해결하기로 생각했다. pair을 이용하여 dp배열을 만들었는데, 첫 번째 원소는 첫 번째 날 떡의 개..
알고리즘 2021. 11. 5. 12:21
백준 12852번 1로 만들기 2 C++

bfs탐색으로 풀 수 있는 문제인데 숫자 n이 1이 되기까지의 숫자들의 정보를 저장해야 하는 문제이다. 우선 최솟값은 bfs탐색을 하면서 쉽게 구할 수 있고, 자신의 이전 값을 저장하는 parent 배열을 만들었다. bfs탐색을 진행하면서 자신의 이전 값을 parent 배열에 저장하고, 숫자가 1이 되면 1부터 parent 배열을 통해 값이 n이 될 때까지 역추적? 하면서 값을 하나씩 저장한다. 저장된 정보를 역순으로 출력하면 n에서 1이 되는 과정의 숫자들이 출력된다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long..
알고리즘 2021. 11. 3. 00:25
백준 10164번 격자상의 경로 C++

직사각형의 경로에서 동그라미가 주어지면 그 곳을 거쳐서 오른쪽 밑 끝까지 가고, 주어지지 않으면 그냥 오른쪽 밑 끝까지 가는 경우의 수를 구하는 문제이다. 동그라미의 좌표가 주어지지 않으면 (0, 0)에서 (n-1, m-1) 까지의 경우의 수를 구하고 동그라미의 좌표가 (x, y)라고 주어지면 (0, 0)에서 (x, y) 경우의 수와 (x, y,)에서 (n-1, m-1)까지의 경우의 수를 곱하면 된다. 동그라미는 좌표가 아닌 숫자로 주어지기 때문에 좌표로 변환해야 한다. 숫자가 k로 주어지면 ( (k - 1) / m , (k - 1) % m ) 의 식을 통해 좌표를 구할 수 있다. bfs방식을 통해서 경우의 수를 구하였다. #include #include #include #include #include ..
알고리즘 2021. 11. 1. 12:57
백준 1309번 동물원 C++

다이나믹 프로그래밍으로 해결할 수 있는 문제이다. 3가지 경우가 있는데, 사자를 배치하지 않는 경우, 왼쪽에 배치하는 경우, 오른쪽에 배치하는 경우가 있다. dp[n][3] 의 dp테이블을 만들어서 0열에는 배치하지 않을 때의 경우의 수, 1열에는 왼쪽에 배치할 때의 경우의 수, 2열에는 오른쪽에 배치할 때의 경우의 수를 넣어서 문제를 해결할 수 있다. 우선 우리의 크기가 1일 때에는 dp[1][0] = 1, dp[1][1] = 1, dp[1][2] =1 로 모두 하나의 경우의 수를 가진다. 다음 우리의 크기가 2일 때에는 사자를 배치하지 않는 경우는 위의 세 가지 경우 모두 가능하기 때문에 dp[2][0]=dp[1][0]+dp[1][1]+dp[1][2] 이다. 사자를 왼쪽에 배치하는 경우는 1행에서 사..
알고리즘 2021. 10. 31. 12:58
이전 Prev 1 ··· 6 7 8 9 10 11 Next 다음