DeJa
Techvu
DeJa
전체 방문자
51,021
오늘
19
어제
54
  • Techvu (60)
    • DesignPatterns (3)
      • 생성 (0)
      • 구조 (1)
      • 행동 (2)
    • Refactoring (0)
    • DataStructures (0)
    • Algorithms (24)
      • 기본 지식 (12)
      • 문제 풀이 (12)
    • OOP (0)
    • TDD (2)
    • DDD (0)
    • Programming Languages (9)
      • Java (9)
      • Kotlin (0)
    • Spring (1)
    • JPA (7)
    • Web (1)
      • 기본 지식 (1)
      • 실무 경험 (0)
    • CS (12)
      • Network (1)
      • OS (8)
      • DataBase (3)
      • Server (0)
    • Git (1)
    • Conferences (0)

블로그 메뉴

  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록

공지사항

  • Study
  • GitHub
  • Medium Blog

인기 글

  • 스키마(Schema)
    2022.01.08
    스키마(Schema)
  • 자바 버전별 역사 및 특징
    2022.01.12
    자바 버전별 역사 및 특징
  • 깃허브 사용 방법
    2021.12.15
    깃허브 사용 방법
  • 동시성 이슈(Concurrency Issue)
    2022.03.20
    동시성 이슈(Concurrency Issue)
  • JPA 는 과연 1차 캐시를 통해서 Repeatable R⋯
    2021.12.27
    JPA 는 과연 1차 캐시를 통해서 Repeatable R⋯

태그

  • JPA
  • network
  • java
  • 알고리즘
  • CS
  • TDD
  • DATABASE
  • Spring
  • 디자인패턴
  • OS
  • web

최근 댓글

  • 글 잘읽고 가요.
    아이폰
  • 컴파일러자체에서 꼬리재귀를 지원하지 않으니 static으로⋯
    aaa
  • 압도적 감사
    ㅇㅇㅇ

최근 글

  • Write a test code right now
    2022.03.24
    Write a test code right now
  • 동시성 이슈(Concurrency Issue)
    2022.03.20
    동시성 이슈(Concurrency Issue)
  • POJO, JavaBean, Entity, VO, DTO
    2022.02.08
    POJO, JavaBean, Entity, VO, DTO
  • TDD with Agile
    2022.02.05
    TDD with Agile
  • Java Stream 기초
    2022.01.23
    Java Stream 기초

티스토리

hELLO · Designed By 정상우.
DeJa

Techvu

이것이 코딩테스트다 : 금광
Algorithms/문제 풀이

이것이 코딩테스트다 : 금광

2022. 1. 7. 18:43
728x90

금광

아이디어

다음 열로 이동하고자 하는 목적지에 대해 아래의 세 가지 경우만 고려하면 된다.

✔ 왼쪽 위에서 오는 경우
✔ 왼쪽에서 오는 경우
✔ 왼쪽 아래에서 오는 경우

위 케이스를 고려한 점화식은 다음과 같다.

$$dp[x][y] = dp[x][y] + max(leftUp, left, leftDown)$$

구현

public class Main {

    static int T;
    static List<int[][]> testcases = new ArrayList<>();
    static int[][] dp;

    public static void main(String[] args) {
        input();
        solution();
    }

    static void input() {
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();

        for (int i = 0; i < T; i++) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[][] graph = new int[n][m];
            for (int x = 0; x < n; x++) {
                for (int y = 0; y < m; y++) {
                    graph[x][y] = sc.nextInt();
                }
            }
            testcases.add(graph);
        }
    }

    static void solution() {
        for (int i = 0; i < testcases.size(); i++) {
            int[][] graph = testcases.get(i);

            int n = graph.length;
            int m = graph[0].length;
            dp = new int[n][m];

            // DP 테이블 초기화
            for (int x = 0; x < n; x++) {
                for (int y = 0; y < m; y++) {
                    dp[x][y] = graph[x][y];
                }
            }

            for (int y = 1; y < m; y++) {
                for (int x = 0; x < n; x++) {
                    int leftUp, leftDown, left;

                    // 왼쪽 위에서 오는 경우, x == 0 일때는 왼쪽 위에서 올 수가 없으니까 0으로 초기화
                    if(x == 0) {
                        leftUp = 0;
                    } else {
                        leftUp = dp[x - 1][y - 1];
                    }

                    // 왼쪽 아래에서 오는 경우, x 가 n - 1 일때는 왼쪽 아래에서 올 수가 없으니까 0으로 초기화
                    if(x == n - 1) {
                        leftDown = 0;
                    } else {
                        leftDown = dp[x + 1][y -1];
                    }

                    // 왼쪽에서 오는 경우
                    left = dp[x][y - 1];

                    // 점화식
                    dp[x][y] = dp[x][y] + Math.max(leftUp, Math.max(leftDown, left));
                }
            }

            int result = 0;
            for (int p = 0; p < n; p++) {
                // 마지막 열에 각 케이스에 대한 최댓값이 존재함
                result = Math.max(result, dp[p][m - 1]);
            }
            System.out.println(result);
        }
    }
}
728x90
저작자표시 비영리 동일조건
  • 카카오스토리
  • 트위터
  • 페이스북

'Algorithms > 문제 풀이' 카테고리의 다른 글

이것이 코딩 테스트다 : 편집 거리  (0) 2022.01.18
[BOJ 18353] 병사 배치하기  (0) 2022.01.11
[BOJ 14502] 연구소  (0) 2022.01.06
[BOJ 15686] 치킨 배달  (0) 2022.01.03
[BOJ 16234] 인구 이동  (0) 2021.12.31
    'Algorithms/문제 풀이' 카테고리의 다른 글
    • 이것이 코딩 테스트다 : 편집 거리
    • [BOJ 18353] 병사 배치하기
    • [BOJ 14502] 연구소
    • [BOJ 15686] 치킨 배달
    알고리즘
    DeJa
    DeJa
    Tech Blog
    댓글쓰기
    [BOJ 18353] 병사 배치하기
    다음 글
    [BOJ 18353] 병사 배치하기
    [BOJ 14502] 연구소
    이전 글
    [BOJ 14502] 연구소

    티스토리툴바