본문 바로가기

동적계획법27

[백준/C,C++] 1520번: 내리막 길 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 풀이 해당 문제를 보고 DFS, BFS문제구나 생각을 했습니다. 관건은 동적계획법을 사용해 어떻게 연산 수를 줄이는 것인가인데 다른 고수분들의 풀이를 보고 참고해 풀었습니다. DP[y][x] = 현재 지점의 좌표가 y, x일 때, 끝지점에 도달할 수 있는 경로의 개수로 가정하고 이를 사용한다면 탐색의 횟수를 줄일 수 있습니다. 예제를 통해 적용해보겠습니다. 최초 출발 지점인 50에서 10으로 갈 수 있.. 2021. 7. 4.
[백준/C,C++] 11049번: 행렬 곱셈 순서 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 풀이 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 개인적으로 11066번: 파일 합치기와 비슷한 문제라 느꼈습.. 2021. 7. 4.
[백준/C,C++] 11066번: 파일 합치기 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 풀이 문제 예제인 40, 30, 30, 50을 보겠습니다. DP[start][end]를 start부터 end까지 합치는 최소비용이라 하고, psum[i]를 0부터 i까지의 파일을 합치는 데 드는 비용이라 했을 때 40, 30, 30, 50의 최소 비용은 다음과 같이 나타낼 수 있습니다. DP[1][4] = min(DP[1][1] + DP[2][4], DP[1][2] + DP[3][4], .. 2021. 7. 4.
[백준/C,C++] 9465번: 스티커 www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 많이 등장하는 비교적 쉬운 난이도의 DP 문제입니다 100에 해당하는 스티커를 떼야 한다고 생각해 봅시다. 빨간색으로 동그라미 쳐진 스티커 두장을 떼고 100점 짜리 스티커를 떼거나 파란색으로 동그라미 쳐진 스티커를 떼고 100점 짜리 스티커를 떼는 방법이 있을 겁니다. 빨간색으로 동그라미 쳐진 스티커를 한장만 떼고 100점 짜리 스티커를 떼는 방법은 고려하지 않아도 됩니다. 두 번째 50점짜리.. 2021. 4. 20.

티스토리툴바