백준 - 설탕 배달(Python) www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그�� www.acmicpc.net 이 문제를 접근할 때 맨처음에 떠오른 생각은 dp를 이용해서 풀어야겠다고 생각했다. dp의 인덱스는 0이 될 수 있는 최소한의 연산 횟수이다. dp[3] = 1, dp[5] =1로 두고 (3과 5일때 바로 그 두 값을 뺄 수 있기 때문에) range(6, 입력값)으로 for문을 돌렸다. for문의 내용은 3으로 뺀값이 최대값이 아닐때(값이 있을 때) 그 수에 +1(연산 횟수)를 해주었..

백준 - 1로 만들기(Python) www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 해석: 위 문제는 다이나믹 프로그래밍을 대표하는 문제이다. 다이나믹 프로그래밍은 어려운 개념은 아니고 필자의 경험대로 풀어쓰자면 긴 수행시간을 줄이거나 메모리를 효율적으로 사용해야 할 경우에 '점화식'과 같은 방법의 활용으로 해결하는 방법이다. 필자가 풀어본 1로 만들기 문제중에 그리디 문제도 있었는데, 동전 거스름돈 문제(그리디)처럼 큰수부터 나누면 최솟값이 당연하게 나오지 않지 않나?라고 생각할 수도 있다. 하지만 큰 수로 나누다가 값이 나눠지지 않아 1로 계속 빼야하는 경우는 오..