문제 |
문제로 가기 -> http://183.106.113.109/30stair/scv/scv.php?pname=scv
난이도: 하
N * N 크기의 맵이 있다. 이 맵에는 미네랄이 군데군데 매장되어 있어서 당신은 SCV 를 이용해 이 미네랄을 채취하려고 한다.
SCV 는 (1,1) 의 위치에서 출발하여 (N,N)까지 이동하는데, 이 SCV 는 고물이라 오른쪽 또는 아래쪽으로 밖에 움직이지 못한다. 이 SCV 는 무한한 양의 미네랄을 가지고 있을 수 있다고 가정하자. 이 SCV 를 이용해서 최대한 많이 미네랄을 얻도록 하는 프로그램을 작성하시오.
입력 방법
- 첫 줄에는 맵의 크기 N ( 3 <= N <= 100)이 주어진다.
- 둘째줄부터는 주어진 지도가 N 줄 만큼 입력된다. (단, 0 은 미네랄 없음, 1 은 미네랄 있음을 의미한다.)
출력 방법
SCV 가 채취할 수 있는 최대 미네랄 양을 출력한다.
입출력 예
입력 5 0 1 0 0 1 0 0 1 0 0 1 0 1 1 0 1 1 0 1 0 1 0 0 0 1 출력 6
내가 푼 방법... |
Backtracking으로 접근하니 재귀를 돌면서 stack overflow가 발생했다.
본 문제는 왔던 길로 다시 돌아가는 경우가 없으니 DP로 푸는 것이 적당하다.
일단 결과를 적어 넣을 배열 하나와 가중치가 적힌 입력 맵을 받을 배열 두개를 만들어 두었다.
[방법1]
처음으로 시도했던 방법은 아래 그림처럼 최상단 가로줄과 가장 왼쪽줄을 모두 계산한 다음 [0][1], [1][0]을 비교하여 [1][1]을 비교하여 마지막 인덱스까지 loop문을 돌렸다. 답은 구할 수 있었지만, 처음 윗줄과 왼쪽 줄을 구하는 과정이 필요하고, [1][1] 부터 표를 채워 나갈 때 [0][0] 인덱스는 제외하고 계산해야하므로 인덱스 조정 과정에서 시간이 많이 소요됐다.
[방법2]
padding을 두어 입력 받는 값보다 map 바깥쪽에 공간을 더 만들어 두었다. 모두 0으로 채워넣고, 앞의 복잡한 과정 없이 [0][1], [1][0]을 비교하여 결과 배열을 채워넣을 수 있었다.
결과는 마지막으로 결과 배열에 채워지는 값을 출력하면 끝난다.
소스 코드 |
'Algorithm > Dovelet' 카테고리의 다른 글
| josephus / 통과율(51%) (0) | 2014.07.02 |
|---|---|
| Block/통과율(61%) (0) | 2014.07.02 |
| 속임수/coci_trik/통과율(63%) (0) | 2014.05.09 |
| [Dovelet] 친구수/amicable (0) | 2013.07.21 |
| [C]약수 구하기 (0) | 2013.07.19 |