공부공간

https://www.acmicpc.net/problem/1890 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 www.acmicpc.net DP는 너무나도 어려운것 같다. 점프는 맵에 표시된 수만큼 오른쪽과 아래로 점프한다. 최종 목적지까지 가는 경로를 찾아주면된다. 중간에 한 지..

준규는 1,1 에서 출발하여 주어진 N,M 까지 이동하며 이동하는 칸의 사탕을 가져간다. N,M 칸에 도달할 때 준규가 가질수 있는 최대의 사탕 개수를 도출하는 문제이다. 해당 문제의 접근법은 다음과 같다. 1. 이동하는 방법은 오른쪽, 아래, 오른쪽 대각선으로 정해져 있다. 2. 준규가 이동할 수 있는 미로 칸마다 사탕을 가져올 수 있는 최대값을 갱신하며 진행한다. 3. 최대값을 갱신할 때, 위 칸에서 내려오는 경우, 대각선 칸에서 내려오는 경우, 왼쪽 칸에서 오는 경우를 비교한다.

BOJ - 2293) 동전 1의 변형 문제이다. 동전 1의 경우, 주어진 금액을 나타내는 최대의 경우의 수를 출력하는 반면 동전 2의 경우 최소 경우의 수로 해당 금액을 나타내는 문제이다. 주의하여 생각해야할 점은 동전 1과 큰 차이가 없다. 1. 동전 1과 같이, 동전의 종류 별 경우의 수를 갱신한다. 2. 경우의 수를 갱신할 때, 배열 d 의 인덱스 값보다 적은 가치의 동전만을 생각한다. 3. 기존의 배열 d의 값과, 도출된 d 의 값을 비교하여, 적은 값을 선택한다. 4. 주어진 k 값이 도출되지 않을 경우(값이 갱신되지 않았을 경우) -1 을 출력한다. d[j] 의 값을 갱신할 때마다 기존의 d[j] 의 값과 배열에서 동전의 가치만큼 뺀 뒤 1을 더해준 값과 비교하여 더 작은 값을 갱신하고, 값이..

특정 금액을 다른 가치를 가진 동전으로 나타낼수 있는 최대 경우의 수를 구하는 문제이다. 기본적인 유형의 동적 프로그래밍 문제이다. 2중 for 문을 사용하여, 주어진 동전의 가치만을 사용할 때의 경우만 생각하며 일정 금액보다 사용할수 있는 동전의 가치가 낮은 경우, 동전의 가치를 뺀 경우의 수를 더하여 갱신함으로써 문제를 해결한다. ex) 4원을 위의 예제 입력으로 나타내는 경우, 예제의 1원만 사용할 경우를 생각하여 배열에 값을 갱신한다. i = 1) d[1]~d[4] = 1 i = 2) d[1] = 1, d[2] 의 경우 입력된 동전의 가치보다 크거나 같기 때문에, 기존의 d[2] 배열에 가지수를 추가하여 준다. d[4] = d[4](1로만 나타낸 경우의 수) + d[2](1과 2, 2로만 나타낸 ..