<백준> 24.07.17에 푼 문제들

1. 카드 구매하기 (Silver 1)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/11052 카드 구매하기 at main · heesoo-park/ForCodeKata

제출 결과

---

언젠가 풀어봤던 유형의 문제여서 금방 해결했다.

정확히는 바텀업 방식으로 금방 해결했다.

탑다운 방식은 잘 떠오르지 않았다. 왜냐하면 2중 for문이었기 때문이다...

 

그래도 알게 된 것은 바텀업에서 탑다운으로 바꿀 때 겉에 있는 변수는 재귀함수의 매개변수로, 안에 있는 변수는 반복문의 변수로 잡으면 된다는 것이다.

 

문제 자체는 차근차근 계산해서 이전 숫자의 값이 최대일 때 지금 값과 계산해 원래 가지고 있던 값보다 큰지 체크하는 것이어서 쉬웠다.

 

작성한 코드는 다음과 같다.

// 탑다운 방식
import java.io.*;
import java.util.*;

public class Main {
    private static int[] price = new int[1001];
    private static int[] dp = new int[1001];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int n = Integer.parseInt(br.readLine());
        
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            price[i] = Integer.parseInt(st.nextToken());
        }
        
        System.out.print(solve(n));
    }
    
    static int solve(int n) {
        if (dp[n] > 0) return dp[n];
        
        for (int i = 1; i <= n; i++) {
            dp[n] = Math.max(dp[n], solve(n - i) + price[i]);
        }
        
        return dp[n];
    }
}

// 바텀업 방식
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 n = Integer.parseInt(br.readLine());
        int[] price = new int[n + 1];
        int[] dp = new int[n + 1];
        
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            price[i] = Integer.parseInt(st.nextToken());
            dp[i] = price[i];
        }
        
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i], dp[j] + price[i - j]);
            }
        }
        
        System.out.print(dp[n]);
    }
}

 

2. 스티커 (Silver 1)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/9465 스티커 at main · heesoo-park/ForCodeKata

제출 결과

---

어떻게 접근해야하나 고민이 많이 됐던 문제였다.

마지막 두 열까지 조건에 맞춰 선택한 최댓값을 행 간에 비교하여 결과값을 출력하는 방식이었다.

다른 행의 i - 1, i - 2 값을 비교하여 넣어줬다.

 

이번에도 바텀업으로 먼저 풀고 탑다운으로 풀었는데 탑다운에서는 0점이 있을 수 있기 때문에 기본 dp 배열 값을 -1로 초기화했다.

 

작성한 코드는 다음과 같다.

// 바텀업 빙식
import java.io.*;
import java.util.*;

public class Main {
    
    private static int[][] sticker;
    private 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));
        StringTokenizer st;
        
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            sticker = new int[2][100001];
            dp = new int[2][100001];
            
            int n = Integer.parseInt(br.readLine());
            for (int i = 0; i < 2; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 1; j <= n; j++) {
                    sticker[i][j] = Integer.parseInt(st.nextToken());                    
                }
            }
            
            if (n <= 2) {
                bw.write(Math.max(sticker[0][1] + sticker[1][2], sticker[1][1] + sticker[0][2]) + "\n");
                continue;
            }
            
            dp[0][1] = sticker[0][1];
            dp[1][1] = sticker[1][1];
            dp[0][2] = sticker[0][2] + sticker[1][1];
            dp[1][2] = sticker[1][2] + sticker[0][1];
            for (int i = 3; i <= n; i++) {
                dp[0][i] = Math.max(dp[1][i - 1], dp[1][i - 2]) + sticker[0][i];
                dp[1][i] = Math.max(dp[0][i - 1], dp[0][i - 2]) + sticker[1][i];
            }
            
            bw.write(Math.max(dp[0][n], dp[1][n]) + "\n");
        }
        
        bw.flush();
        bw.close();
    }
}


// 탑다운 방식
import java.io.*;
import java.util.*;

public class Main {
    
    private static int[][] sticker;
    private 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));
        StringTokenizer st;
        
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            sticker = new int[2][100001];
            dp = new int[2][100001];
            
            int n = Integer.parseInt(br.readLine());
            for (int i = 0; i < 2; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 1; j <= n; j++) {
                    sticker[i][j] = Integer.parseInt(st.nextToken());
                    dp[i][j] = -1;                  
                }
            }
            
            if (n <= 2) {
                bw.write(Math.max(sticker[0][1] + sticker[1][2], sticker[1][1] + sticker[0][2]) + "\n");
                continue;
            }
            
            dp[0][1] = sticker[0][1];
            dp[1][1] = sticker[1][1];
            dp[0][2] = sticker[0][2] + sticker[1][1];
            dp[1][2] = sticker[1][2] + sticker[0][1];
            
            bw.write(Math.max(solve(0, n), solve(1, n)) + "\n");
        }
        
        bw.flush();
        bw.close();
    }
    
    static int solve(int r, int c) {
        if (c <= 2) return dp[r][c];
        if (dp[r][c] >= 0) return dp[r][c];
        
        if (r == 0) {
            dp[r][c] = Math.max(solve(1, c - 1), solve(1, c - 2)) + sticker[r][c];
        } else {
            dp[r][c] = Math.max(solve(0, c - 1), solve(0, c - 2)) + sticker[r][c];
        }
        
        return dp[r][c];
    }
}