본문 바로가기

DP

 (45)
[백준 / BOJ] 17485 진우의 달 여행 (Large) 문제 출처 : www.acmicpc.net/problem/17485 17485번: 진우의 달 여행 (Large) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2 ≤ N, M ≤ 1000)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net 진우가 지구에서 출발해서 달에 도착했을때, 필요한 자금을 최소화 하는문제다. 달에서 지구까지 가는길에 각 칸에 자금이 주어진다. 풀이 N,M이 각각 최대 1000이고, 한 인덱스에서 아래로 갈수있는방향이 3가지 (왼쪽아래 오른쪽아래 중간) 이므로 완전탐색으로 풀려고하면 시간초과가 난다. 다이나믹 프로그래밍으로 풀어야 했는데, dp배열을 구현하고 사용하는게 힘..
[백준 / BOJ] 2410 2의 멱수의 합 문제 출처 : www.acmicpc.net/problem/2410 2410번: 2의 멱수의 합 첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 자연수 N을 입력받았을때, 그 자연수를 2의 멱수의 합으로 나타내는 경우의수를 구하시오 예를들어 3 1 + 1 + 1 1 + 2 두가지 경우로 나타낼수있다. 풀이 www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 입력받은 동전들을 ..
[백준 / BOJ] 13325 이진트리 문제 출처 : www.acmicpc.net/problem/13325 13325번: 이진 트리 문제 각 에지에 양수인 가중치가 부여된 높이가 k인 포화이진트리가 주어져 있다. 높이 k인 포화이진트리는 2k개의 리프를 포함하여 (2k+1 − 1)개의 노드를 가진다. 루트에서 어떤 리프까지의 거�� www.acmicpc.net 1~K높이의 이진트리가 주어졌을때, 한 루트에서 어떤 리프까지의 거리는 루트에서 그 리프까지의 경로상에 있는 모든 에지들의 가중치를 더한 값이다. 각 에지들의 가중치를 증가시켜서 루트에서 모든 리프까지의 거리가 모두 같게하면서 에지의 가중치합을 최소로 만드는 문제다. 풀이 (백준에서 1초에 반복문이 1억번 돈다고 들은것같다..) 최악의 경우인 1^1 + 1^2 + 1 ^ 3 + ... ..
[백준 / BOJ] 1937 욕심쟁이 판다 문제 출처 : www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net N*N크기의 대나무 숲에있는 판다는 한 지역의 대나무를 다 먹으면 상하좌우중 한 방향으로 움직일수있다. 단, 이때 움직인곳은 전 지역보다 대나무가 많아야한다. 풀이 9달전에 풀다가 틀렸었는데, 알고리즘 공부를 더 하고서야 맞췄다. (9달전에는 바텀업 구현을 못해서 풀지 못했음) DFS와 DP를 합친 문제다. 1. (i ~ N) (j ~ N) 까지 전부다 돌려준다. 2. (i,j)점에서 시..
[백준 / BOJ] 1932 정수 삼각형 문제 출처 : www.acmicpc.net/problem/1932 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최� www.acmicpc.net 정수 삼각형을 입력받았을때, 합이 최대가 되는경로를 찾는문제이다 (각 층에선 한 정수만 더 할수있음) 예를들어 을 입력받으면, 최대경로는 1 -> 3 -> 6 = 10이 된다. 풀이 N을 입력을 받고 정수삼각형의 각 정수 입력마다 최댓값을 찾아줬다. 위 정수삼각형에서 규칙을 찾을수있는데, 1층에는 정수가 1개, 2층에는 정수가 2개 ,3층에는 3개...순으로 늘어..

티스토리툴바