어떤 문제인가?

메모이제이션을 이용해 최댓값을 구하는 문제.

시행착오 횟수

한 번에 성공.

관찰

1. 예제 코드를 보면 알 수 있듯, 행의 크기는 곧 열이다. 예를 들어 제 3열이라면 행의 크기는 3이다(1,2,3행).
2. 맨 왼쪽과 오른쪽을 제외한 중간에 있는 수들은 자신의 위에 있는 좌측, 우측 수 중 최댓값을 이용해야 한다.

1차 시도 : AC

맨 왼쪽 인덱스는 0, 맨 오른쪽 인덱스는 열과 같음을 이용했다. 문제에서는 최댓값을 요구하므로, 기준은 최댓값으로 잡았다.

#include <stdio.h>

int D[500][500];

int main()
{
	int N,i,j,M=0;
	scanf("%d",&N);
	for(i=0;i<N;i++) {
		for(j=0;j<=i;j++) scanf("%d",&D[i][j]);
		if(i) {
			for(j=0;j<=i;j++) {
				if(!j) D[i][j]+=D[i-1][j];
				else if(j==i) D[i][j]+=D[i-1][j-1];
				else D[i][j]+=D[i-1][j-1]>D[i-1][j]?D[i-1][j-1]:D[i-1][j];
			}
		}
	}
	for(j=0;j<N;j++)
		if(M<D[i-1][j]) M=D[i-1][j];
	printf("%d",M);
}

전에 풀었던 1149번 문제에서 반성하여, 이번에는 대입 연산자(+=)를 직접 사용했다.

다른 분들의 풀이

덧셈은 교환법칙이 성립한다. 그러니까 내려오면서 더하는 것도 되지만, 거슬러 올라가는 것도 가능하다.

또한 최댓값을 이용한다는 문제 조건 특성상, 0으로 초기화 된 부분은(예를 들어 삼각형의 맨 왼쪽보다 더 왼쪽에 있는 부분) 무조건 제외된다. 이를 이용하면 코드를 더 줄일 수 있다.

#include <stdio.h>
#define MAX(a,b) (a>b ? a : b)
int main()
{
	int i,j,n,A[501][501];
	scanf("%d",&n);
	for(i=1;i<=n;i++) for(j=1;j<=i;j++) scanf("%d",A[i]+j);
	for(i=n-1;i;i--) for(j=1;j<=i;j++)
		A[i][j]+=MAX(A[i+1][j],A[i+1][j+1]);
	printf("%d",A[1][1]);
	return 0;
}

f52985님의 소스
-> https://www.acmicpc.net/source/358547

그리고 C언어 매크로를 정의해서 쓸 수 있음을 알았다. 나중에 필요한 때 나도 써봐야겠다.

한줄평

기존에 이미 비슷한 유형을 풀어본 덕에 무난한 문제였다.