[이코테][Java] 금광

2025. 4. 10. 17:55·PS/이코테

문제 설명

n × m 크기의 금광의 각 칸에 특정한 크기의 금이 들어있고, 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다.

- 맨 처음에는  첫 번째 열의 어느 행에서든 출발할 수 있다.

- 이후에 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 한다.

위의 규칙을 가지고 이동할 때, 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요.

 

입력조건

  • 첫째 줄에 테스트 케이스 T
  • 매 테스트 케이스의 첫째 줄에 n과 m
  • 매 테스트 케이스의 둘째 줄에 n × m개의 금의 개수

출력조건

  • 테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기

입출력 예시  

입력예시 출력예시
2
3 4
1 3 3 2 2 1 4 1 0 6 4 7
4 4
1 3 1 4 2 2 4 1 5 0 2 3 0 6 1 2
19
16

 

 

 

 

문제 풀이

  • 다이나믹 프로그래밍으로 풀이
  • 금광의 모든 위치에 대해서, 이전 위치일 수 있는 3가지 경우(왼쪽 위에서 오는 경우, 왼쪽에서 오는 경우, 왼쪽 아래에서 오는 경우)를 구하고
  • 그 중에서 가장 많은 금을 현재 위치의 금에 더한다.
  • 위의 방식으로 dp 테이블을 모두 채운 후, 가장 오른쪽 열에서 금의 크기가 가장 큰 것을 구한다.
  • 점화식으로 표현하면 아래와 같다.
dp[i][j] = dp[i][j] + max(dp[i-1][j-1], dp[i][j-1], dp[i+1][j-1])
import java.io.*;
import java.util.*;

public class Main {

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

        int t = Integer.parseInt(br.readLine());

        for (int tc = 0; tc < t; tc++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            int[][] array = new int[n][m];
            int[][] dp = new int[n][m];

            //금광 정보 입력
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    array[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            //dp 테이블 초기화
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    dp[i][j] = array[i][j];
                }
            }

            //dp 시작
            for (int j = 1; j < m; j++) {
                for (int i = 0; i < n; i++) {
                    int left_up, left_down, left;
                    //왼쪽 위 -> dp[i-1][j-1]
                    if (i == 0) {
                        left_up = 0;
                    } else {
                        left_up = dp[i - 1][j - 1];
                    }

                    //왼쪽 -> dp[i][j-1]
                    left = dp[i][j - 1];

                    //왼쪽 아래 -> dp[i+1][j-1]
                    if (i == n - 1) {
                        left_down = 0;
                    } else {
                        left_down = dp[i + 1][j - 1];
                    }
                    dp[i][j] = dp[i][j] + Math.max(left_up, Math.max(left, left_down));
                }
            }

            int result = 0;
            for (int i = 0; i < n; i++) {
                result = Math.max(result, dp[i][m - 1]);
            }
            System.out.println(result);
        }
    }
}

 

 

  ✔️ 처음에 생각했던 idea

  • 맨 처음에는 첫 번째 열에서 금이 가장 많은 행에서 출발한다.
  • 이후에는 현재 위치를 기준으로 다음 위치가 될 수 있는 3가지 경우(오른쪽 위, 오른쪽, 오른쪽 아래) 중에 가장 많은 금이 위치한 곳으로 이동하면서 금의 최대값을  구한다.
  • 하지만 이 풀이는 다음과 같은 반례가 존재한다.
    • 위의 내용을 따르면 주황색처럼 이동해서 금의 크기는 13이 된다.
    • 하지만 여기서 얻을 수 있는 금의 최대 크기는 파란색처럼 이동해서 17이다. 

[참고서적]

이것이 취업을 위한 코딩 테스트다 with 파이썬 by 나동빈

 

저작자표시 비영리 변경금지 (새창열림)

'PS > 이코테' 카테고리의 다른 글

[이코테] 다이나믹 프로그래밍(Dynamic Programming)  (0) 2025.04.12
[이코테][Java] 정수 삼각형  (0) 2025.04.12
[이코테][Java] 경쟁적 전염  (0) 2025.02.14
[이코테][Java] 만들 수 없는 금액  (0) 2025.02.14
[이코테][Java] 무지의 먹방 라이브  (0) 2025.02.14
'PS/이코테' 카테고리의 다른 글
  • [이코테] 다이나믹 프로그래밍(Dynamic Programming)
  • [이코테][Java] 정수 삼각형
  • [이코테][Java] 경쟁적 전염
  • [이코테][Java] 만들 수 없는 금액
nyrimmm
nyrimmm
  • nyrimmm
    개발기록
    nyrimmm
  • 전체
    오늘
    어제
  • 글쓰기 관리
    • 분류 전체보기 (69)
      • Java (6)
      • Spring & SpringBoot (3)
      • Network (1)
      • DataBase (0)
      • SQL (1)
      • IntelliJ (3)
      • Git (0)
      • 자료구조 & 알고리즘 (2)
      • 트러블 슈팅 (1)
        • Spring (1)
      • PS (51)
        • 백준 (11)
        • 프로그래머스 (0)
        • SQL (9)
        • 이코테 (31)
      • 후기 & 회고 (1)
  • 태그

  • 인기 글

  • 최근 글

  • 최근 댓글

  • hELLO· Designed By정상우.v4.10.3
nyrimmm
[이코테][Java] 금광
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.