다이나믹프로그래밍 (2) 썸네일형 리스트형 [백준] 1463 - 1로 만들기 아이데이션이렇게 문제를 딱 봤을 때, 1차원 배열이 머릿속에 그려지고 징검다리 퐁퐁(?) 건너는 듯한 문제는보통 그래프(DFS/DBF) 나 다이나믹 프로그래밍으로 풀리는 경우가 많았다이 문제는 그래프보다는 다이나믹 프로그래밍으로 풀어야 한다고 생각했는데 이유는 다음과 같다1. 주어진 숫자가 계속해서 감소하기만 한다더하는 연산이 없기 때문에 한번 감소하면 다시 증가할 수 없다.즉 숫자의 변화가 한 방향으로만 계속 된다.만약 중간에 증가하는 연산이 있다면, 타겟값을 찾을 때까지 숫자들이 계속 연결되는 그래프 형태를 띄기 때문에그래프 형태로 문제를 푸는 것이 맞다2. 최솟값을 찾는다이건 꼭 다이나믹 프로그래밍 만의 특성이라고는 볼 수 없지만!!아무튼 다이나믹 프로그래밍 문제에서 많이 나오는 조건이여서 넣었다 .. [백준] 2294 - 동전 2 보자마자 다이나믹 프로그래밍으로 풀어야겠구나 생각했던 문제이다. n = 3, k = 7, 동전은 2, 5, 7가 있다고 가정했을 때를 살펴보자. k 0 1 2 3 4 5 6 7 동전 개수 0 inf inf inf inf inf inf inf 2, 5, 7의 가치를 가진 동전으로는 k == 1을 만들 수 없으므로 계속 inf이다. k 0 1 2 3 4 5 6 7 동전 개수 0 inf 1 inf inf inf inf inf 2의 가치를 가진 동전으로 k == 2를 만들 수 있으므로, cache[2]는 cache[2 - 2] + 1과 cache[2] 중 작은 수인 cache[2 - 2] + 1 = cache[0] + 1 = 1이 된다. 이런 식으로 cache를 채워나가면, k 0 1 2 3 4 5 6 7 동전.. 이전 1 다음
