728x90 Dynamic 썸네일형 리스트형 [백준알고리즘] 1890번: 점프 -Python [백준알고리즘] 1890번: 점프 -Python https://www.acmicpc.net/problem/1890 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 www.acmicpc.net 재귀를 사용한 동적계획법으로 문제를 풀었다. 동적 계획법으로 풀 수 있는 문제이다 보니 여러 .. 더보기 [백준알고리즘] 2294번: 동전 2 -Python [백준알고리즘] 2294번: 동전 2 -Python https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다. www.acmicpc.net 동적 계획법을 사용해서 문제를 풀었다. 주어진 코인으로 1부터 k까지 차례대로 만들 때 사용하는 코인의 최소 개수를 저장하도록 했다. 각 금액을 만들 때 모든 코인들을 사용해본다. 현재 만들려는 금액이 t라면, 각 코인을 사용해서 t가 되었다고 생각을 하면 된다. 주어진 예제입력을 예시로 들어보겠다... 더보기 [백준알고리즘] 2163번: 초콜릿 자르기 -Python [백준알고리즘] 2163번: 초콜릿 자르기 -Python https://www.acmicpc.net/problem/2163 2163번: 초콜릿 자르기 정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다. 초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿을 친구들과 나눠 먹기로 했다. 이를 위해서 정화는 초콜릿을 계속 쪼개서 총 N×M개의 조각으로 쪼개려고 한다. 초콜릿을 쪼갤 때에는 초콜릿 조각을 하나 들고, 적당한 위치에서 초콜릿을 쪼갠다. 초콜릿을 쪼갤 때에는 금이 가 있는 위치에서만 쪼갤 수 있다. 이와 www.acmicpc.net 처음에는 Dynamic Programming 방식으로 풀었다. NxM크기의 .. 더보기 [백준알고리즘] 1463번: 1로 만들기 -Python [백준알고리즘] 1463번: 1로 만들기 -Python https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 동적 계획법(DP)문제이다. 이제 이런 거에 연연하면 안 될 것 같은 게.... DP 문제임을 알게 되니까 당연히 케이스를 나눠서 해야지! 재귀를 부르고 Top-Down 형태로 할거야! 이런 식으로 생각이 들게 된다. 그런데 이 문제는 이런 방식으로 풀었더니 안됐다... 그러고 보니 -1이 자꾸 거슬렸다. -1 때문에 결국에는 1부터 N까지 모든 수의 최소 연산 수를 계산하기 때문이다. 그러다 보니 초과가 뜬것이라 생각하고 Bottom-Up 형태로 1부터 .. 더보기 이전 1 2 다음