본문 바로가기
Problem Solving/백준

[백준] 1932번 : 정수 삼각형

by shinbian11 2020. 2. 25.

출처 : https://www.acmicpc.net/problem/1932

 

1932번: 정수 삼각형

문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는

www.acmicpc.net

#include <stdio.h>
int numbermax(int m, int n)
{
	int ans = m > n ? m : n;
	return ans;
}
int arr[501][501] = { 0, };
int main()
{
	int n, max = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			scanf("%d", &arr[i][j]);
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			if (j == 1) arr[i][j] += arr[i - 1][j];
			else if (j == i) arr[i][j] += arr[i - 1][j - 1];
			else arr[i][j] += numbermax(arr[i - 1][j - 1], arr[i - 1][j]);
			if (max < arr[i][j])
				max = arr[i][j];
		}
	}
	printf("%d\n", max);
}

다이나믹 프로그래밍 관련 문제는 처음 풀어봤는데... 이걸 노가다로 구현하고 머리싸맸을 생각하니 정말 끔찍하네요..

얼른얼른 새로운 개념들을 빨리 많이 배워야겠어요!

또한 중첩 for문을 하나로 합칠수도 있습니다. 

저는 아직 초보라, 보기 편하게 구현할 때 일부로 구분을 해놓았는데, 중첩 for문을 하나로 합치면 코드 길이가 줄겠죠!

'Problem Solving > 백준' 카테고리의 다른 글

[백준] 2523번: 별 찍기 - 13  (0) 2020.03.15
[백준] 1436번 : 영화감독 숌  (0) 2020.02.29
[백준] 2751번 : 수 정렬하기 2  (0) 2020.02.24
[백준] 10773번 : 제로  (0) 2020.02.24
[백준] 10828번 : 스택  (0) 2020.02.24