정해인

문제 : https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 어떤 문제인가? 설탕을 n킬로그램을 배달해야 한다. 설탕은 3kg, 5kg 봉지로만 존재해 이 두 가지 종류의 봉지만 사용하여 배달을 해야 한다. 이때, 배달에 필요한 최소 봉지의 개수를 출력하면 된다. 이 문제는 예전에 그리디 알고리즘을 공부할 때 풀었던 문제이다. 지금은 다이내믹 프로그래밍을 공부 중인데 문제가 있어서 이번엔 dp로 풀어보았다. https://codegarden-farmjun.t..

문제 : https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 어떤 문제인가? 이친수라는 문제에서 정의된 이진수들이 있다. n이 입력됐을 때 n자리 이친수의 개수를 출력하면 된다. 접근 방법 일단 문제가 dp(다이나믹 프로그래밍)이라는 것은 문제를 읽으면 알 수 있다. 그러므로 점화식을 세워야한다. n = 1일 때 1 1개 n = 2일 때 10 1개 n = 3일 때 101 100 2개 n = 4일 때 1001 1010 1000 3개 . ...