문제 보기https://www.acmicpc.net/problem/14916  풀이힌트를 보면 그리드, DP를 사용할 수 있는 문제인 것 같다.나는 DP가 더 익숙해서 DP를 사용하였다.즉 거스름 돈이 0부터 N원일 때까지 얼마가 나올지를 계산해보는 방법을 선택했다. int[] dp = new int[N 우선 0~5까지는 미리 값을 계산하여 넣어 놨다.혹시나 input으로 5보다 작은 값이 들어올 경우에도 dp 배열의 크기를 6으로 하도록 했다.여기서 -1이 나와야 하는 값의 경우 100000이라는, 절대 나올리 없는 임의의 큰 값을 넣었다. for (int i = 6; i 이후 반복문을 돌리며5원 더 작은 값에서 5원을 추가한 상황,2원 더 작은 값에서 2원을 추가한 상황 중 더 작은 경우를 골랐다.만..

문제보기 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net DP(다이나믹 프로그래밍)을 사용하는 문제이다. 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 점화식을 세우기 위해 규칙을 파악할 필요가 있다. 정수 1, 2, 3을 나타내는 방법을 파악해보자. 1: 1 2: 1+1, 2 3: 1+1+1,..

문제보기 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 언뜻 보아도 DP(다이나믹 프로그래밍)를 사용하는 문제이다. 마지막 계단까지 점수의 Max 값을 구하면 되지만, 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 조건이 까다롭기 때..