<백준> 24.07.03에 푼 문제들

1. 돌 게임 (Silver 5)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/9655 돌 게임 at main · heesoo-park/ForCodeKata

제출 결과

---

처음에는 그냥 1 또는 3이고 합치면 무조건 짝수가 되는 걸 이용해서 2로 나눴을 때 나머지가 있으면 CY를, 없으면 SK를 출력하는 식으로 풀었다.

하지만 DP 문제를 DP를 잘 활용하지 못 한 거 같아 다른 사람들의 풀이를 보니까 내가 보통 풀 때 int형 DP 배열을 만드는데 여기서는 boolean형 DP 배열로 만들더라

 

1부터 3까지는 직관적으로 알 수 있으니 미리 초기화를 하고 그 이후는 반복문을 돌면서 3으로 나눠진다면 현재 개수 - 3 위치의 값을 반전하여 저장하고, 나눠지지 않는다면 현재 개수 - 1 위치의 값을 반전하여 저장했다.

 

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

import java.io.*;
import java.util.*;

public class Main {
    
    static boolean[] dp = new boolean[1001];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        
        dp[1] = true;
        dp[3] = true;
        for (int i = 4; i <= n; i++) {
            dp[i] = (i % 3 == 0) ? !dp[i - 3] : !dp[i - 1];
        }
        
        System.out.print(dp[n] ? "SK" : "CY");
    }
}

 

2. 1로 만들기 (Silver 3)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/1463 1로 만들기 at main · heesoo-park/ForCodeKata

제출 결과

---

1로 만들기지만 풀 때는 n 만들기처럼 풀었다.

1부터 시작해서 차근차근 올라가며 dp 배열을 채워나갔다.

 

처음에는 그냥 3으로 나눠지는지, 2로 나눠지는지, 이전 값 순서로 하며 모든 과정마다 Math.min을 붙여줬는데 이러다보니까 배열의 초기화가 필요해지며 시간이 좀 늘어났다.

그래서 어떻게 하면 되나 했는데 이전 값을 가장 먼저 수행하여 무조건 1을 크게 만들어놓고 이후에 2나 3으로 나눠지는지 체크하는 방식으로 하면 됐다..!

 

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

import java.io.*;
import java.util.*;

public class Main {
    
    static int[] dp = new int[1000001];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + 1;
            
            if (i % 2 == 0) dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            
            if (i % 3 == 0) dp[i] = Math.min(dp[i], dp[i / 3] + 1);
        }
        
        System.out.print(String.valueOf(dp[n]));
    }
}

 

3. 1, 2, 3 더하기 (Silver 3)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/9095 1, 2, 3 더하기 at main · heesoo-park/ForCodeKata

제출 결과

---

이 문제는 처음에 풀었을 때는 감이 정말 안 왔던 문제인데 여러번 보다보니 눈에 보이는게 생겼다.

 

맨 앞의 숫자는 1, 2, 3까지 가능하고 그럼 뒤에 붙는 케이스는 현재 숫자 - 1, - 2, - 3 된 숫자들의 경우의 수일 것이다.

그렇기 때문에 4의 경우에 3의 경우의 수 앞에 1이 붙어 4개가, 2의 경우의 수 앞에 2가 붙어 2개가, 1의 경우의 수 앞에 3이 붙어 1개가 더해져서 7개가 나오는 것이다.

이러한 흐름이 계속 이어져서 dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1] (i >= 4) 가 된다.

 

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

import java.io.*;
import java.util.*;

public class Main {
    
    static int[] dp = new int[11];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int t = Integer.parseInt(br.readLine());
        
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for (int i = 4; i < 11; i++) {
            dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
        }
        
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            bw.write(dp[n] + "\n");
        }
        
        bw.flush();
        bw.close();
    }
}

 

4. 계단 오르기 (Silver 3)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/2579 계단 오르기 at main · heesoo-park/ForCodeKata

제출 결과

---

이 문제는 어떻게 조건에 맞는 움직임을 하는지 확인하는게 방법이 잘 안 떠올랐다.

특히 2번째 조건인 연속된 세 개의 계단을 모두 밟아서는 안 된다는게 걸렸다.

 

그래도 찾아낸 방법은 아래에서부터 위로 반복문을 돌면서 (현재 칸 - 2 위치의 dp 값)과 (현재 칸 - 1 위치의 점수 + 현재 칸 - 3 위치의 dp 값)을 비교하여 큰 값을 챙기고 현재 칸 점수를 더하는 거였다.

현재 칸 - 2 위치의 dp 값을 사용하면 무조건 두 칸이 떨어져있기 때문에, 그리고 dp 값이니 조건을 현재 칸 - 2까지 만족하며 왔기 때문에 조건에 참인 값이다.

또한 현재 칸 - 1 위치의 점수 + 현재 칸 - 3 위치의 dp 값도 마찬가지로 처음에 두 칸 올라오고 다음에 한 칸 올라와서 현재 칸에 온 것이기 때문에 조건에 참인 값이다.

이 두 가지 값만이 현재 위치에 도달할 수 있는 방법이다.

 

현재 칸 - 1 위치의 dp 값을 쓰지 않고 점수를 쓴 것은 dp 값이 조건을 만족하면서 왔긴 했는데 이전 과정을 따로 체크하지 않아 알 수 없기 때문이다.(...라고 생각한다.)

 

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

import java.io.*;
import java.util.*;

public class Main {
    
    static int[] scores = new int[301];
    static int[] dp = new int[301];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        for (int i = 1; i <= n; i++) {
            scores[i] = Integer.parseInt(br.readLine());
        }
        
        dp[1] = scores[1];
        
        if (n == 1) {
            System.out.print(String.valueOf(dp[1]));
            return;
        }
        
        dp[2] = scores[1] + scores[2];
        for (int i = 3; i <= n; i++) {
            dp[i] = Math.max(dp[i - 2], scores[i - 1] + dp[i - 3]) + scores[i];
        }
        
        System.out.print(String.valueOf(dp[n]));
    }
}