<백준> 24.07.15에 푼 문제들

1. 쉬운 계단 수 (Silver 1)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/10844 쉬운 계단 수 at main · heesoo-park/ForCodeKata

제출 결과

---

이걸 어떻게 접근하지... 하다가 직접 계단수를 써내려가는데 이전 단계의 양쪽 값을 더하는 규칙이 보이기 시작했다.

그래서 처음에 1차원 배열로 뒀던 DP 배열을 2차원 배열로 변경하고 각 단계에 따른 1~9까지의 dp 값을 저장했다.

 

바텀업 방식은 금방 해결할 수 있었는데 탑다운 방식은 아직 잘 막힌다.

바텀업 방식의 dp 배열을 채우는 코드를 재귀 함수 내에서 재귀 함수 호출로 바꿔야한다는 것을 이해는 했지만 반복문과 재귀의 차이에서 오는 부분은 아직 어색하다.

특히 바텀업에서는 반복 범위를 직접 조절할 수 있어서 9에 대한 처리를 따로 안 해줬지만 탑다운에서는 그게 안 되서 9에 대한 조건 처리를 따로 해줘야했다.

 

그리고 재귀로 할 때는 이미 값이 있는 부분을 다시 처리하지 않도록 조건을 넣어 끊어주는 것이 필요했다.

이걸 하지 않으면 시간초과가 나왔다.

 

여러번 틀렸었는데 이건 sum 변수를 long이 아니라 int로 설정해서 생긴거였다.

그것도 모르고 이곳저곳 모듈러 연산 넣었었다...ㅎㅎ

 

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

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

public class Main {
    
    private static long[][] dp = new long[101][11];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        for (int i = 0; i < 10; i++) {
            dp[1][i] = 1;            
        }
        
        int n = Integer.parseInt(br.readLine());
        
        long sum = 0;
        for (int i = 0; i < 10; i++) {
            sum += solve(n, i);
        }
        System.out.print(sum % 1000000000);
    }
    
    static long solve(int n, int i) {
        if (n == 1) {
            return (i != 0) ? 1 : 0;
        }
        
        if (dp[n][i] != 0) return dp[n][i];
        
        if (i == 0) dp[n][i] = solve(n - 1, i + 1);
        else if (i == 9) dp[n][i] = solve(n - 1, 8);
        else dp[n][i] = (solve(n - 1, i - 1) + solve(n - 1, i + 1)) % 1000000000;
        
        return dp[n][i];
    }
}


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

public class Main {
    
    private static long[][] dp = new long[101][11];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        for (int i = 0; i < 10; i++) {
            dp[1][i] = 1;            
        }
        
        for (int i = 2; i < 101; i++) {
            for (int j = 0; j < 10; j++) {
                if (j == 0) dp[i][j] = dp[i - 1][j + 1];
                else dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
            }
        }
        
        int n = Integer.parseInt(br.readLine());
        
        long sum = 0;
        for (int i = 1; i < 10; i++) {
            sum += dp[n][i];
        }
        System.out.print(sum % 1000000000);
    }
}

 

2. 포도주 시식 (Silver 1)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/2156 포도주 시식 at main · heesoo-park/ForCodeKata

제출 결과

---

계단 오르기 문제가 생각나는 문제였고 그대로 진행했더니 당연히 틀렸다.

왜냐하면 이 문제는 마지막 계단에 도착할 수 있는 케이스의 최대값이 아니라 모든 케이스에 대해서 최대값을 구하는 것이기 때문이다.

그래도 연속 3잔이 안된다는 조건이 있었기에 기본 골격은 그대로 갔다.

하지만 틀렸던 것이기 때문에 무슨 조건이 필요할까 알아보니까 현재 포도주를 안 먹는 케이스가 더 많이 마실 수도 있는 케이스를 이전 조건을 체크한 후에 한번 더 체크해야했다.

dp[i]와 dp[i - 1]를 한번 더 체크하는 거다...!!

 

배열 안에 있는 값들 중에 최댓값을 찾기 위해 Stream API 안에 있는 Arrays.stream().max() 함수를 사용했다.

그런데 max()까지만 쓰면 출력값이 int 형이 아니었기 때문에 getAsInt() 메서드를 붙여줬다.

 

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

// 바텀업 방식
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));
        
        int n = Integer.parseInt(br.readLine());
        int[] glass = new int[n + 1];
        int[] dp = new int[n + 1];
        
        for (int i = 1; i <= n; i++) {
            glass[i] = Integer.parseInt(br.readLine());
        }
        
        dp[1] = glass[1];
        
        if (n == 1) {
            System.out.print(dp[1]);
            return;
        }
        
        dp[2] = glass[1] + glass[2];
        for (int i = 3; i <= n; i++) {
            dp[i] = Math.max(dp[i - 1], Math.max(dp[i - 2], glass[i - 1] + dp[i - 3]) + glass[i]);
        }
        
        System.out.print(Arrays.stream(dp).max().getAsInt());
    }
}