Zayson
A to Zayson!
Zayson
전체 방문자
오늘
어제
  • 분류 전체보기 (132)
    • Computer Science (20)
      • Network (4)
      • DB (12)
      • OS (4)
    • Algorithm (32)
      • 완전탐색(Brute-Force) (3)
      • 그리디(Greedy) (6)
      • 투포인터(Two-Pointer) (1)
      • 그래프(Graph) (5)
      • BFS & DFS (9)
      • 구현, 시뮬레이션(Implementation) (5)
      • 다이나믹 프로그래밍(DP) (3)
    • Backend (51)
      • Spring Boot (19)
      • JPA (16)
      • Kafka (2)
      • Java (13)
      • Kotlin (1)
    • DevOps (1)
      • Jenkins (5)
      • Oracle Cloud Infrastructure (1)
      • Kubernetes & Docker (1)
    • Trouble Shooting (3)
      • JPA (1)
      • Spring Boot (2)
    • 회고 (5)
      • 엔빵 프로젝트 포스트 로드맵 (1)
      • 2022년 (4)
    • Kafka (7)
      • Kafka (5)
      • Kafka Connect (2)
    • 기술 서적 (6)
      • 데이터 중심 애플리케이션 설계 (3)
      • 개발자가 반드시 정복해야할 객체 지향과 디자인 패턴 (2)
      • 가상 면접 사례로 배우는 대규모 시스템 설계 기초 (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

인기 글

태그

  • 그리디
  • Java
  • 나 혼자 스프링부트!
  • 관계형 데이터베이스 실전 입문
  • Computer science
  • 구현
  • SpringBoot
  • 프로그래머스
  • spring boot
  • 엔빵프로젝트
  • dfs
  • 완전탐색
  • Kafka Connect
  • 라이브스터디
  • CS
  • BFS
  • JPA
  • kafka
  • Backend
  • 백준

최근 글

티스토리

hELLO · Designed By 정상우.
Zayson

A to Zayson!

[백준, Java] 9465번 : 스티커
Algorithm/다이나믹 프로그래밍(DP)

[백준, Java] 9465번 : 스티커

2022. 5. 19. 22:44

🔗 문제 링크

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

😮 문제 해결 방법

매 열마다 1행 혹은 2행의 스티커를 뜯었을 때의 최대 점수를 구해주면 되기 때문에 2차원 배열로 선언해준다.

최대 점수는 n열까지 모두 뜯었을 때 1행 n열 혹은 2행 n열의 점수 중 큰 점수가 가장 최대로 구할 수 있는 점수이다.

 

현재 열이 3열이라고 가정하고 스티커를 뜯는 경우를 판단해보자.

3열의 스티커를 뜯는 경우는 1행 3열, 2행 3열의 스티커를 뜯는 경우 2가지이다.

1행 3열의 스티커를 뜯는 경우 → row : 0 col : 2

 

  • 인접한 변을 가진 스티커는 뜯을 수 없기 때문에 **이전 열 대각선(현재 행과 반대되는 행)**에 위치한 최대 점수 값과 현재 스티커 점수를 더해준다. → dp[prevRow][col - 1] + sticker[row][col]
    • row가 0이므로 대각선의 row는 1일 것이고, 이전 열이기 때문에 이전 열은 col -1이다.

 

  • 한 칸 띄워진 경우는 1행 2행 모두 현재 스티커와 인접하지 않기 때문에 둘 중하나를 뜯어줄 수 있다.
    • 한 칸 띄워진 1행을 뜯는 경우 : dp[0][col-2] + sticker[row][col]
    • 한 칸 띄워진 2행을 뜯는 경우 : dp[1][col-2] + sticker[row][col]

2행 3열의 스티커를 뜯는 경우도 1행 3열의 스티커를 뜯는 것과 이전 열에 대한 행만 반대로 판단해주면 된다.

 

이렇게 최대로 구할 수 있는 방법을 하나의 점화식으로 나타내보면 아래와 같다.

dp[row][col] = Math.max(sticker[row][col] + dp[prevRow][col - 1], Math.max(sticker[row][col] + dp[0][col - 2], sticker[row][col] + dp[1][col - 2]))

 

모든 열에 대해 최대 점수를 구하고, 마지막 열의 두 행 중 최대 점수를 리턴해준다.

🚩 Java 코드

package com.algorithm.Baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_9465_스티커 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        for (int loop = 0; loop < T; loop++) {
            int N = Integer.parseInt(br.readLine());
            int[][] sticker = new int[2][N];

            for (int row = 0; row < 2; row++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int col = 0; col < N; col++) {
                    sticker[row][col] = Integer.parseInt(st.nextToken());
                }
            }

            int rst = getMaxScore(N, sticker);
            System.out.println(rst);
        }

        br.close();
    }

    private static int getMaxScore(int n, int[][] sticker) {
        if (n == 1) return Math.max(sticker[0][0], sticker[1][0]);
        if (n == 2) return Math.max(sticker[0][0] + sticker[1][1], sticker[0][1] + sticker[1][0]);

        // 각 열마다 획득할 수 있는 최대 점수
        int[][] dp = new int[2][n];
        dp[0][0] = sticker[0][0];
        dp[1][0] = sticker[1][0];
        dp[0][1] = dp[1][0] + sticker[0][1];
        dp[1][1] = dp[0][0] + sticker[1][1];

        /**
         * row : 현재 행, col : 현재 열
         * 1. sticker[row][col]을 뜯는 경우 기준
         * 2. dp[0][col-2], dp[1][col-2] 처럼 한 칸 띄워진 경우이므로 두 행의 점수 중 큰 값을 가져와 더해줄 수 있다.
         * 3. dp[prevRow][col - 1] 현재 스티커 기준 이전 열의 대각선에 위치한 점수만 가져올 수 있다.
         * 점화식 : dp[row][col] = Math.max(sticker[row][col] + dp[prevRow][col - 1], Math.max(sticker[row][col] + dp[0][col - 2], sticker[row][col] + dp[1][col - 2]))
         */

        // 매 열마다 최대로 얻을 수 있는 점수 구하기
        for (int col = 2; col < n; col++) {
            for (int row = 0; row < 2; row++) {
                int prevRow = row == 1 ? 0 : 1;
                dp[row][col] = Math.max(sticker[row][col] + dp[prevRow][col - 1], Math.max(sticker[row][col] + dp[0][col - 2], sticker[row][col] + dp[1][col - 2]));
            }
        }

        return Math.max(dp[0][n - 1], dp[1][n - 1]);
    }
}
반응형
저작자표시 비영리 변경금지 (새창열림)

'Algorithm > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[백준, Java] 5557번 : 1학년  (0) 2022.07.10
[프로그래머스, Java] 땅따먹기  (0) 2022.07.10
    'Algorithm/다이나믹 프로그래밍(DP)' 카테고리의 다른 글
    • [백준, Java] 5557번 : 1학년
    • [프로그래머스, Java] 땅따먹기
    Zayson
    Zayson
    공부한 내용을 정리하는 공간

    티스토리툴바