[BOJ] 1932 정수 삼각형 - JAVA

1. 문제

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 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

---

2. 풀이

규칙

내가 찾은 규칙은 다음과 같다. (그림에 써진 숫자는 인덱스 번호다)

• 삼각형을 층 번호(그림에서 N)로 나누어서 생각할 때, 그 층에 있는 요소의 개수는 층 번호(N)와 동일하다.
• 그리고, 선택된 인덱스에서 값을 더할 수 있는 위층의 요소들(편의상 부모라고 칭한다)은 해당 인덱스에서 N, N-1을 뺀 값으로 접근할 수 있다.
• 그림에서처럼 12인덱스의 부모 요소는 12-5=7, 12-4=8인 것이다. 
• 만약 해당 층에서 1번째 요소거나 N번째 요소라면 왼쪽과 오른쪽 끝 요소라는 의미이므로 부모 요소가 하나밖에 없는 것을 유의해야 한다.

 

코드

• 삼각형 값을 저장할 배열 크기는 1+2+...+N = N*(N+1)/2이다.  
• n은 층 번호, i는 해당 층의 인덱스번호다.
• 인덱스 값을 더해가면서 요소를 비교한다.
  • 먼저 현재 인덱스의 삼각형 값을 입력받는다.
  • i=1(첫 번째 요소)이라면 맨 왼쪽 요소이므로 왼쪽 부모는 비교하지 않는다.
  • i=n(마지막 요소)이라면 맨 오른쪽 요소이므로 오른쪽 부모는 비교하지 않는다.
  • 위의 두 경우를 제외하고 오른쪽 부모와 왼쪽 부모를 비교해서 현재 인덱스 값에 더한다.
• 최댓값을 알기 위해 층 번호(n)가 마지막일 때 max값을 요소마다 비교한다.

public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   StringTokenizer st;

   int N = Integer.parseInt(in.readLine());
   int[] triangle = new int[N*(N+1)/2];

   int idx = 0;int max = Integer.MIN_VALUE;
   for(int n=1;n<=N;n++){
      st = new StringTokenizer(in.readLine());
      for(int i=1;i<=n;i++,idx++){
         triangle[idx] = Integer.parseInt(st.nextToken());
         int tmp = Math.max(i!=1?triangle[idx-n]:0, i!=n?triangle[idx-n+1]:0);
         triangle[idx] += tmp;

         if(n==N) max = Math.max(max,triangle[idx]);
      }
   }

   System.out.println(max);

}

---

3. 결과

규칙을 찾는 데 많은 시간이 걸렸던 문제였다.