[알고스팟] DIAMONDPATH

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • DIAMONDPATH
  • 2000ms
  • 65536kb
  • 2288
  • 995 (43%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 연습문제
  • 보기

문제

6 
   1 2 
  6 7 4
 9 4 1 7
6 7 5 9 4
 4 4 3 2 
  1 2 3 
   6 1
    7

위 그림과 같이 자연수들이 다이아몬드 형태대로 배치되어 있다. 이 때, 각 가로줄에서 한 개씩의 숫자를 골라 맨 위에서 맨 아래칸으로 내려오는 경로를 구성하고 싶다. 경로에서 앞뒤에 위치한 숫자들은 서로 인접해 있어야 한다: 예를 들어, 위 그림에서 세 번째 줄의 7 은 그 아랫 줄의 4 또는 1 과만 이어질 수 있다.

이와 같은 경로 중, 포함된 숫자의 합이 가장 큰 경로를 찾고 해당 숫자의 합을 계산하시오.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 100) 가 주어진다. 각 테스트 케이스의 첫 줄에는 다이아몬드 가운데 줄의 가로 길이 N (1 <= N <= 100) 이 주어진다. 그 후 2*N-1 줄에, 맨 윗 줄부터, 다이아몬드의 각 가로줄에 속한 숫자가 왼쪽부터 순서대로 주어진다. 각 수는 100 이하의 자연수라고 가정해도 좋다.

출력

각 테스트 케이스마다 한 줄에 숫자들의 합이 가장 큰 경로에 대해 해당 합을 출력한다.

예제 입력

2
5
6
1 2
6 7 4
9 4 1 7
6 7 5 9 4
4 4 3 2
1 2 3
6 1
7
5
39
43 16
74 94 24
25 76 98 62
79 58 71 67 98
43 55 27 44
10 96 56
73 31
95

예제 출력

48
664

---

DP 기본...은 아니고 미묘하게 심화된 기본문제

양자화에서 이미 기가 다 빨려서 ㅠ 시벌탱~~~

재귀로 풀어야되는데 귀찮아서 안햇다~~~~~

알빠야~~~~~ 힘드렁~~~~

제출해보니 왠걸 바로 정답처리 ㄱㅇㄷ

printBoard 함수는 걍 만들어놈 보기쉽게 ㅎㅎ

public class DiamondPath {

    static  int[][] resultBoard;
    static int[][] board;
    static int N;
    public static void main(String[] args) throws Exception{
        StringBuilder sb = new StringBuilder();
        java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));

        int num = Integer.parseInt(br.readLine());
        for(;num>0;num--){

            N = Integer.parseInt(br.readLine());
            resultBoard = new int[2*N-1][N];
            board = new int[2*N-1][N];


            for(int x=0;x<2*N-1;x++){

                doDP(x,br.readLine());
            }
            sb.append(resultBoard[2*N-2][0]).append('\n');
        }
        System.out.println(sb.toString());
    }

    public static String printBoard(int[][] board, int n){
        StringBuilder sb = new StringBuilder();
        sb.append("==========================\n");
        for(int x=0;x<2*n-1;x++){
            for(int y = 0; y < n; y++) {
                sb.append(board[x][y]+"\t");
            }
            sb.append("\n");
        }
        sb.append("==========================\n");
        System.out.println(sb.toString());
        return sb.toString();
    }
    public static void doDP(int x, String line){
        if(x==2*N-1) return ;

        if(x==0) {
            resultBoard[0][0] = Integer.parseInt(line);
        }else {
            int result;

            int beforeNum;
            int afterNum;
            int y = 0;
            for(String s : line.split(" ")) {
                if (x < N) {
                    beforeNum = y-1;
                    afterNum = y;
                } else {
                    beforeNum = y;
                    afterNum = y + 1;
                }

                if (beforeNum < 0) result = resultBoard[x - 1][afterNum] + Integer.parseInt(s);
                else if (afterNum >= N) result = resultBoard[x - 1][beforeNum] + Integer.parseInt(s);
                else {
                    result = Math.max(resultBoard[x - 1][beforeNum],resultBoard[x - 1][afterNum]) + Integer.parseInt(s);
                }
                resultBoard[x][y] = result;
                y++;
            }
        }
    }
}

시간되면 리팩토링하고~~ 아님말고~~~ 인생뭐잇어~~