<백준> 24.07.10에 푼 문제들

1. 피보나치 수의 확장 (Silver 3)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/1788 피보나치 수의 확장 at main · heesoo-park/ForCodeKata

제출 결과

---

어려운 문제일 줄 알았는데 음수에 대해서 직접 적어보니까 부호의 변화만 있을 뿐 숫자 진행은 양수와 동일했다.

 

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

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));
        StringBuilder sb = new StringBuilder();
        
        int n = Integer.parseInt(br.readLine());
        int absN = Math.abs(n);
        
        if (n == 0) {
            sb.append(0).append("\n").append(0);
            System.out.print(sb);
            return;
        }
        
        long[] dp = new long[Math.abs(absN) + 1];
        
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= absN; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000000;
        }
        
        if (n < 0) {
            if (absN % 2 == 0) {
                sb.append(-1).append("\n");
            } else {
                sb.append(1).append("\n");
            }
        } else {
            sb.append(1).append("\n");
        }
        sb.append(dp[absN]);
        
        System.out.print(sb);
    }
}

 

2. 돌 게임 3 (Silver 3)

[백준]

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

[깃허브]

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

제출 결과

---

마지막에 돌 가져간 사람이 이기는데 1, 3, 4개가 남아있으면 이번에 뽑는 사람이 이기는 거다.

true가 SK, false가 CY가 이기는 걸로 정했다.

그런데 dp[i - 1], dp[i - 3], dp[i - 4]가 모두 true라면 항상 CY가 이기는 방법이 존재하는 것이기 때문에 dp[i]가 false가 된다.

그리고 하나라도 false라면 SK가 이기는 방법이 존재하는 것이기 때문에 완벽하게 게임을 하는 특성 상 dp[i]가 true가 된다.

 

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

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));
        
        dp[1] = true;
        dp[2] = false;
        dp[3] = true;
        dp[4] = true;
        for (int i = 5; i < 1001; i++) {
            if (dp[i - 1] && dp[i - 3] && dp[i - 4]) {
                dp[i] = false;
            } else {
                dp[i] = true;
            }
        }
        
        int n = Integer.parseInt(br.readLine());
        System.out.print(dp[n] ? "SK" : "CY");
    }
}

 

3. 연속합 (Silver 2)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/1912 연속합 at main · heesoo-park/ForCodeKata

제출 결과

---

처음에는 누적합을 생각했지만 누적합으로는 O(N^2)인 방법밖에 생각 안나서 포기했다.

DP를 사용하는 Kadane's Algorithm을 사용했다.(이런 이름이 있는 줄은 chatGPT한테 물어보고 알게 됐다.)

dp배열에 현재 위치까지의 최대부분합을 저장하며 반복문을 진행하고 가장 큰 값을 계속 업데이트하며 가장 큰 연속합을 구하는 방식이다.

이 알고리즘은 O(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 max = -1001;
        
        int n = Integer.parseInt(br.readLine());
        int[] nums = new int[n + 1];
        int[] dp = new int[n + 1];
        
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }
        
        for (int i = 1; i <= n; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            max = Math.max(max, dp[i]);
        }
        
        System.out.print(max);
    }
}