코드업 3703번

이 글에서는 코드업 3703번 문제를 풀이해보도록 하겠습니다.

https://codeup.kr/problem.php?id=3703 

사탕 줍기 1

---

문제 설명

 

N행 M열의 맵이 있다.

치원이는 (1행, 1열)에 있고, 엄마는 (N행, M열)에서 기다리고 있다.

치원이는 엄마에게 가야하며, 맵의 상, 하, 좌, 우로만 움직일 수 있다.

그리고 맵에는 치원이가 좋아하는 사탕이 곳곳에 존재한다. (한 칸에 여러개의 사탕이 있을 수도 있다.)

가장 짧은 길로 가면서 사탕을 최대한 많이 얻는 것이 목표이다.

엄마에게 도착했을 때 치원이가 얻을 수 있는 최대 사탕수를 출력하는 프로그램을 작성하시오.

예) 아래와 같은 (4, 3)의 맵에서는 최대 10개의 사탕을 얻을 수 있다.

0	3	0
2	1	2
0	0	3
5	2	1

(1, 1) - (2, 1) - (3, 1) - (4, 1) - (4, 2) - (4, 3)

---

입력

 

첫째 줄에 행의 수 N과 열의 수 M이 입력된다. (1 <= N, M M <= 100)

둘째 줄부터 N+1행까지 맵의 정보가 입력된다. (숫자는 그 위치의 사탕 수를 의미한다.)

---

출력

 

가장 짧은 길로 가면서 얻을 수 있는 최대 사탕수를 출력한다.

문제를 해석해보면, (1, 1)에서 (N, M)까지 이동을 할 텐데, 중간의 이동 경로에 있는 숫자를 다 더했을 때 그 최댓값은 얼마인가를 묻는 문제입니다.

음... 모든 경우를 다 따져보는 코드를 짤 수는 있겠지만, 좀 느릴 것 같습니다. 그래서 메모이제이션을 사용하려고 합니다.

이 문제를 푸는데 핵심은 "최단 경로로 움직인다"는 것이라고 생각합니다. 그 조건이 있기 때문에, 움직이는 것은 무조건 아래쪽 또는 오른쪽으로만 움직이게 되고, 그렇기 때문에 재귀함수 점화식을 간단하게 쓸 수 있습니다. (N, M)칸까지 이동했을 때 경로 합의 최댓값은 (N-1, M)칸까지의 최댓값과 (N, M-1)칸까지의 최댓값 중 큰 값에 (N, M)칸의 값을 더한 것으로 생각할 수 있는 것이죠. 

이러한 아이디어를 바탕으로, 순서도를 짜봅시다.

전체 순서도

핵심 함수 f의 순서도

.사실 처음에는 아래와 같이 코드를 짜보았는데, 오류가 났습니다.

#include <stdio.h>

int n, m;
int a[101][101];
int mem[101][101];
int chk[101][101];

int f(int x, int y)
{
	if(x == 0 || y == 0)
	{
		return 0;
	}
	
	if(chk[x][y] == 0)
	{
		chk[x][y] = 1;
		return mem[x][y] = f(x-1, y)>f(x, y-1)?f(x-1, y):f(x, y-1) + a[x][y];
	}
	else
	{
		return mem[x][y];
	}
}

int main()
{
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			scanf("%d", &a[i][j]);
		}
	}
	
	printf("%d", f(n, m));
}

다시 살펴보니, 이중반복문을 돌릴 때 아래와 같이 범위를 수정해주어야 설계한 함수에 맞게 돌아가고, 삼항연산자도 전체를 괄호로 묶어주어야 오류가 나지 않았습니다.

for(int i = 1; i <= n; i++)
{
	for(int j = 1; j <= m; j++)
	{
		scanf("%d", &a[i][j]);
	}
}

이러한 점을 반영한 것이 위의 순서도이고, 이를 바탕으로 짠 올바른 코드는 아래와 같습니다.

#include <stdio.h>

int n, m;
int a[101][101];
int mem[101][101];
int chk[101][101];

int f(int x, int y)
{
	if(x == 0 || y == 0)
	{
		return 0;
	}
	
	if(chk[x][y] == 0)
	{
		chk[x][y] = 1;
		return mem[x][y] = (f(x-1, y)>f(x, y-1)?f(x-1, y):f(x, y-1)) + a[x][y];
	}
	else
	{
		return mem[x][y];
	}
}

int main()
{
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			scanf("%d", &a[i][j]);
		}
	}
	
	printf("%d", f(n, m));
}

코드 설명을 간단하게만 해보면, n, m값을 입력받고, 지도를 입력받아 배열 a에 저장합니다. 이제 f(n, m)을 실행시켜 그 결과를 출력할 것인데, f함수의 실행 과정은 다음과 같습니다. 우선 x 또는 y가 0이면 맵 밖으로 벗어난 것이므로 0을 반환해주고, 만약 (x, y)칸을 계산한 적이 없다면, 즉 chk[x][y] 값이 0이라면 1로 바꾸어주고  (f(x-1, y)>f(x, y-1)?f(x-1, y):f(x, y-1)) + a[x][y] 값을 계산해주어 mem[x][y]에 저장합니다. (왜 저 값을 계산하는 지는 위에서 설명했으므로 생략하겠습니다.) 또는, 이미 계산한 적이 있는 칸이라면, 즉 chk[x][y] 값이 1이라면 mem[x][y] 값을 불러와 반환해줍니다.

---

이렇게 코드업 3703번 문제를 풀이해보았습니다.