Cooper's devlog

스티커:9465번 - JAVA 본문

Algorithm/Baekjoon

스티커:9465번 - JAVA

cooper_dev 2020. 7. 16. 04:01

1. 문제 링크

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

 

9465번: 스티커

문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티

www.acmicpc.net

 

2. 문제 설명

3. 문제 접근

-dp문제는 주로 규칙성을 찾고 점화식을 작성하는 것이 핵심이다!!

(하지만, 최댓값, 최솟값을 구하는 문제을 규칙성으로 접근하는 것이 쉬운 것만은 아닌 것 같다.)

 

1. 첫번 째 문제 접근 법

(1) 이전의 값이 일치 함에 따라서 if문을 작성하여 일치하는 경우 분류해서 접근하는 방식으로 접근하려고 했다.

 

 

2. 문제 접근 해결법

- 생각보다 간단한 원리에 의해 점화식이 작성되는 것을 확인할 수 있었다.

(1) 이전의 최댓 값이 다음 데이터의 합이 되는지 확인하는 문제.

                dp[1][k] = Math.max(dp[2][k-1], dp[2][k-2]) + data[1][k];

                dp[2][k] = Math.max(dp[1][k-1], dp[1][k-2]) + data[2][k];

(쉽다고 얘기할 수도 있겠지만, 당장 점화식을 작성하는 과정에서 생각보다 시간이 오래걸렸던 점화식)

 

 

4. 문제 풀이

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Sticker {
    static int[][] data;
    static int[][] dp;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        
        for (int t = 1; t <= T; t++) {
            int n = Integer.parseInt(br.readLine());
            data = new int[3][n+1];
            dp = new int[3][n+1];
            
            for (int row = 1; row <= 2; row++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int col = 1; col <= n; col++) {
                    data[row][col] = Integer.parseInt(st.nextToken());
                }
            }
            
            dp[1][1] = data[1][1];
            dp[2][1] = data[2][1];
            
            for (int k = 2; k <= n; k++) {
                dp[1][k] = Math.max(dp[2][k-1], dp[2][k-2]) + data[1][k];
                dp[2][k] = Math.max(dp[1][k-1], dp[1][k-2]) + data[2][k];
            }
            
            System.out.println(Math.max(dp[1][n], dp[2][n]));
        }
    }
}
 
  

5. 느낀 점 혹은 접근법

(1) 간단한 점화식을 작성하는 과정에성 최대, 최소를 구하는 점화식은 단계적으로 접근해서 문제를 작성하는 것이 더 효율적이라고 판단한다.

 

'Algorithm > Baekjoon' 카테고리의 다른 글

정수 삼각형: 1932번 - JAVA  (0) 2020.07.16
포도주 시식:2156번-JAVA  (0) 2020.07.16
RGB거리 : 1149번 - JAVA  (0) 2020.07.16
오르막수:11057번 - JAVA  (0) 2020.07.15
RGB거리 : 1149번 - JAVA  (0) 2020.07.15
'Algorithm/Baekjoon' Related Articles more
Comments