갓생사는 김초원의 개발 블로그
chocho_log
갓생사는 김초원의 개발 블로그
전체 방문자
오늘
어제
  • 분류 전체보기 (77)
    • 개발 (22)
      • Spring (4)
      • Java (3)
      • Database (2)
      • Elasticsearch (3)
      • ETC (3)
      • JPA (3)
      • 이슈 (1)
    • 코딩 테스트 (43)
      • 프로그래머스 (23)
      • 백준 (12)
      • TIP (8)
    • 자료구조 (2)
    • 알고리즘 (4)
    • 잡생각 (0)
    • 경험 (5)
      • AWS re:Invent 2024 (5)

블로그 메뉴

    공지사항

    인기 글

    태그

    • jar
    • 디자인패턴 #SOLID 원칙
    • querydsl
    • jpa
    • Lazy Loading
    • 지연로딩
    • war
    • Spring Boot Embedded Tomcat

    최근 댓글

    최근 글

    갓생사는 김초원의 개발 블로그

    chocho_log

    [백준][Sliver1]1932 - 정수 삼각형 - JAVA
    코딩 테스트/백준

    [백준][Sliver1]1932 - 정수 삼각형 - JAVA

    2021. 6. 20. 16:10

    [문제]

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

     

    1932번: 정수 삼각형

    첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

    www.acmicpc.net

     

    [풀이]

    * 알고리즘: 다이나믹 프로그래밍

    다이나믹 프로그래밍을 이용하여 푸는 문제이다. 

    점화식은 쉽게 세울수 있다.

    그런데 인덱스를 이용한 삼각형 배열을 만드는 것이 어려웠다.

    어려웠던 이유는 1차원 배열로 삼각형을 만드려했기 때문이었다.

    2차원 배열로 삼각형을 만드니 쉽게 다이나믹프로그래밍을 이용하여 문제를 풀 수 있었다. 

     

    바텀업 방식으로 풀면되는데 현재 위치에서 위로 왼쪽 대각선, 오른쪽 대각선에 있는 수 중 큰 수를 현재값과 더해주면 된다.

    그런데 삼각형 매 줄에 가장 왼쪽 숫자는 위에 왼쪽 대각선에 숫자가 없고, 가장 오른쪽 숫자는 위에 가장 오른쪽 숫자가 없다.

    그래서 가장 왼쪽 숫자와 가장 오른쪽 숫자는 비교 필요없이 한쪽 대각선에 있는 숫자만 더해주면 된다.

    [코드]

    package com.algorithm.thisiscodingtest.dp;
    
    import java.io.*;
    import java.util.StringTokenizer;
    
    public class PreviousProblem02 {
        public static int N;
        public static int[][] dp;
    
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
            N = Integer.parseInt(br.readLine());
            dp = new int[N][N];
    
            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                int index = 0;
                while (st.hasMoreTokens()) {
                    int num = Integer.parseInt(st.nextToken());
                    dp[i][index] = num;
                    index++;
                }
            }
    
            solution();
    
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < dp[N - 1].length; i++) {
                max = Math.max(max, dp[N - 1][i]);
            }
    
            bw.write(max + "\n");
    
            br.close();
            bw.flush();
            bw.close();
        }
    
        public static void solution() {
            for (int i = 1; i < N; i++) {
                for (int j = 0; j <= i; j++) {
                    if (j == 0) {
                        dp[i][j] += dp[i - 1][j];
                    } else if (j == i) {
                        dp[i][j] += dp[i - 1][j - 1];
                    } else {
                        dp[i][j] += Math.max(dp[i - 1][j - 1], dp[i - 1][j]);
                    }
                }
            }
        }
    }
    

    '코딩 테스트 > 백준' 카테고리의 다른 글

    [백준][Gold2]10473 - 인간 대포 - JAVA  (0) 2021.07.07
    [백준][Gold5]1107 - 리모컨 -JAVA  (0) 2021.05.20
    [백준][Gold5] 12865 - 평범한 배낭 - JAVA  (0) 2021.05.16
    [백준][gold5] 9251번: LCS - JAVA  (0) 2021.05.09
    [백준][gold5] 14502번: 연구소 - JAVA  (0) 2021.05.08
      '코딩 테스트/백준' 카테고리의 다른 글
      • [백준][Gold2]10473 - 인간 대포 - JAVA
      • [백준][Gold5]1107 - 리모컨 -JAVA
      • [백준][Gold5] 12865 - 평범한 배낭 - JAVA
      • [백준][gold5] 9251번: LCS - JAVA
      갓생사는 김초원의 개발 블로그
      갓생사는 김초원의 개발 블로그
      갓생사는 김초원의 개발 블로그 github: https://github.com/kimchowon

      티스토리툴바