<div id="readability-page-1" class="page"><div tabindex="-1" id="___gatsby"><header><h2><a href="/">김로그</a></h2><nav><a href="/tags">tags</a>|<a href="/about">about</a></nav></header><main><article><header><time datetime="September 08, 2016">September 08, 2016</time><a rel="tag" href="/tags#다이나믹-프로그래밍">#다이나믹 프로그래밍</a> <a rel="tag" href="/tags#백준온라인저지">#백준온라인저지</a> </header><section><a href="https://www.acmicpc.net/problem/1932" target="_blank" rel="noopener">1932번 숫자삼각형</a>
문제의 주어진 삼각형에서 꼭대기에서 한칸씩 내려오며 방문한 점들 합의 최대값을 구하는 문제이다. 윗 층에서 아래층으로 내려갈 때 왼쪽 대각선 혹은 오른쪽 대각선 으로만 이동할 수 있다.
이 문제는 <a href="/algo/2016/05/15/Algo0-dynamic-programing/">다이나믹프로그래밍</a>으로 풀 수 있다. 우선 문제의 예시로 주어진 삼각형은 다음과 같다.
<div data-language="text"><pre><code> 7
 3 8
 8 1 0
 2 7 4 4
 4 5 2 6 5</code></pre></div>
위 삼각형을 2차원 배열로 나타내면 아래와 같이 나타낼 수 있는데
<table>
<thead>
<tr>
<th>행/열</th>
<th>0</th>
<th>1</th>
<th>2</th>
<th>3</th>
<th>4</th>
</tr>
</thead>
<tbody>
<tr>
<td>0</td>
<td>7</td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr>
<td>1</td>
<td>3</td>
<td>8</td>
<td></td>
<td></td>
<td></td>
</tr>
<tr>
<td>2</td>
<td>8</td>
<td>1</td>
<td>0</td>
<td></td>
<td></td>
</tr>
<tr>
<td>3</td>
<td>2</td>
<td>7</td>
<td>4</td>
<td>4</td>
<td></td>
</tr>
<tr>
<td>4</td>
<td>4</td>
<td>5</td>
<td>2</td>
<td>6</td>
<td>5</td>
</tr>
</tbody>
</table>
행렬에서 아래층 이동은 <code>num[행][열]</code> &gt; <code>num[행 + 1][열]</code> 혹은 <code>num[행][열]</code> &gt; <code>num[행 + 1][열 + 1]</code> 이 된다. 
이동하면서 최대값이 저장될 배열 <code>ret</code>를 선언하고 <code>num[행][열]</code>까지의 최대값을 <code>ret[행][열]</code>에 저장한다.
이렇게 이전 단계의 답을 다음단계의 답을 구하는데 활용할 수 있으므로 다이나믹 프로그래밍으로 풀 수 있다.
<div data-language="cpp"><pre><code>ret[0][0] = num[0][0];
for(int i = 0 ; i &lt; N-1 ; i++){
 for(int j=0; j &lt;i + 1 ;j++){
 if( ret[i+1][j] &lt; ret[i][j] + num[i+1][j]) // 왼쪽 대각선 이동
 ret[i+1][j] = ret[i][j] + num[i+1][j];
 if( ret[i+1][j+1] &lt; ret[i][j] + num[i+1][j+1]) // 오른쪽 대각선 이동
 ret[i+1][j+1] = ret[i][j] + num[i+1][j+1];
 }
}</code></pre></div>
전체 소스코드
<div data-language="c"><pre><code>#include &lt;cstdio&gt;

int main(){
	int N;
	long long num[501][501]={0,};
	long long ret[501][501]={0,};
	scanf("%d",&amp;N);

	for(int i = 0 ; i &lt; N ; i++){
		for(int j=0; j &lt;i + 1 ;j++){
			scanf("%lld",&amp;num[i][j]);
		}
	}

	ret[0][0] = num[0][0];
	for(int i = 0 ; i &lt; N-1 ; i++){
		for(int j=0; j &lt;i + 1 ;j++){
			if( ret[i+1][j] &lt; ret[i][j] + num[i+1][j])
				ret[i+1][j] = ret[i][j] + num[i+1][j];
			if( ret[i+1][j+1] &lt; ret[i][j] + num[i+1][j+1])
				ret[i+1][j+1] = ret[i][j] + num[i+1][j+1];
		}
	}

	long long max = 0;
	for(int i = 0 ; i &lt; N ; i++){
		if(ret[N-1][i] &gt; max)
			max = ret[N-1][i] ;
	}
	printf("%lld\n",max);

	return 0;
}</code></pre></div>
<hr>
<h2>reference</h2>
<ul>
<li><a href="https://www.acmicpc.net/problem/1932" target="_blank" rel="noopener">1932번 숫자삼각형</a></li>
<li><a href="https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95" target="_blank" rel="noopener">동적계획법 - 나무위키</a></li>
<li><a href="https://www.youtube.com/embed/0o2hF-To_6Q" target="_blank" rel="noopener">다이나믹 프로그래밍 시작하기 - 스타트링크</a></li>
</ul></section><hr></article><nav><ul><li><a rel="prev" href="/beakjoon/2016-09-02-2193/">← 2193번 이친수</a></li><li><a rel="next" href="/beakjoon/2016-09-08-11403/">11403번 경로 찾기 →</a></li></ul></nav></main></div></div>

Kimlog RSS Feed

KIM, WOOJUNG

1932번 숫자삼각형
문제의 주어진 삼각형에서 꼭대기에서 한칸씩 내려오며 방문한 점들 합의 최대값을 구하는 문제이다. 윗 층에서 아래층으로 내려갈 때 왼쪽 대각선 혹은 오른쪽 대각선 으로만 이동할 수 있다.
이 문제는 다이나믹프로그래밍으로 풀 수 있다. 우선 문제의 예시로 주어진 삼각형은 다음과 같다.
 7
 3 8
 8 1 0
 2 7 4 4
 4 5 2 6 5
위 삼각형을 2차원 배열로 나타내면 아래와 같이 나타낼 수 있는데
행/열
0
1
2
3
4
0
7
1
3
8
2
8
1
0
3
2
7
4
4
4
4
5
2
6
5
행렬에서 아래층 이동은 num[행][열] > num[행 + 1][열] 혹은 num[행][열] > num[행 + 1][열 + 1] 이 된다.
ret를 선언하고 num[행][열]까지의 최대값을 ret[행][열]에 저장한다.
이렇게 이전 단계의 답을 다음단계의 답을 구하는데 활용할 수 있으므로 다이나믹 프로그래밍으로 풀 수 있다.
ret[0][0] = num[0][0];
for(int i = 0 ; i < N-1 ; i++){
 for(int j=0; j <i + 1 ;j++){
 if( ret[i+1][j] < ret[i][j] + num[i+1][j]) // 왼쪽 대각선 이동
 ret[i+1][j] = ret[i][j] + num[i+1][j];
 if( ret[i+1][j+1] < ret[i][j] + num[i+1][j+1]) // 오른쪽 대각선 이동
 ret[i+1][j+1] = ret[i][j] + num[i+1][j+1];
 }
}
전체 소스코드
#include <cstdio>
int main(){
	int N;
	long long num[501][501]={0,};
	long long ret[501][501]={0,};
	scanf("%d",&N);
	for(int i = 0 ; i < N ; i++){
		for(int j=0; j <i + 1 ;j++){
			scanf("%lld",&num[i][j]);
		}
	}
	ret[0][0] = num[0][0];
	for(int i = 0 ; i < N-1 ; i++){
		for(int j=0; j <i + 1 ;j++){
			if( ret[i+1][j] < ret[i][j] + num[i+1][j])
				ret[i+1][j] = ret[i][j] + num[i+1][j];
			if( ret[i+1][j+1] < ret[i][j] + num[i+1][j+1])
				ret[i+1][j+1] = ret[i][j] + num[i+1][j+1];
		}
	}
	long long max = 0;
	for(int i = 0 ; i < N ; i++){
		if(ret[N-1][i] > max)
			max = ret[N-1][i] ;
	}
	printf("%lld\n",max);
	return 0;
}
reference
1932번 숫자삼각형
동적계획법 - 나무위키
다이나믹 프로그래밍 시작하기 - 스타트링크

1932번 숫자삼각형

댓글