<백준> 24.07.08에 푼 문제들

1. 피보나치 함수 (Silver 3)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/1003 피보나치 함수 at main · heesoo-park/ForCodeKata

제출 결과

---

그려보니까 0에 대한 값, 1에 대한 값을 따로 계산해서 dp 배열에 따로 저장하면 되겠다는 견적이 나왔다.

 

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

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

public class Main {
    
    private static int[][] dp = new int[41][2];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        dp[0][0] = 1;
        dp[1][1] = 1;
        for (int i = 2; i < 41; i++) {
            dp[i][0] = dp[i - 1][0] + dp[i - 2][0];
            dp[i][1] = dp[i - 1][1] + dp[i - 2][1];
        }
        
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            
            sb.append(dp[n][0]).append(' ').append(dp[n][1]).append("\n");
        }
        
        System.out.print(sb);
    }
}

 

2. 2×n 타일링 2 (Silver 3)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/11727 2xn 타일링 2 at main · heesoo-park/ForCodeKata

제출 결과

---

이 문제를 풀면서 첫번째 케이스가 최대값인 1000이라는 걸 알게 됐다.

범위를 1000까지 포함 안 시켰더니 다른 걸 아무리 만져도 통과하지 못했기 때문이다...ㅎㅎ

 

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

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

public class Main {
    
    private static long[] dp = new long[1001];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        dp[1] = 1;
        dp[2] = 3;
        for (int i = 3; i < 1001; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 10007;
        }
        
        int n = Integer.parseInt(br.readLine());
        System.out.print(dp[n]);
    }
}

 

3. 이친수 (Silver 3)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/2193 이친수 at main · heesoo-park/ForCodeKata

제출 결과

---

이번에도 1부터 차근차근 그려보는데 맨 앞의 1을 떼고 바로 1다시 못 붙이니까 0떼고 나니까 0부터 시작하는 이전 값의 형태가 보이고 1부터 시작하는 그 이전 값의 형태도 보이더라

 

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

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

public class Main {
    
    private static long[] dp = new long[91];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i < 91; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        int n = Integer.parseInt(br.readLine());
        System.out.print(dp[n]);
    }
}

 

4. 파도반 수열 (Silver 3)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/9461 파도반 수열 at main · heesoo-park/ForCodeKata

제출 결과

---

dp 배열을 계산할 때 1,2,3까지만 미리 초기화해야한다는 생각을 깨준 문제

 

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

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

public class Main {
    
    private static long[] dp = new long[101];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        dp[1] = 1;
        dp[2] = 1;
        dp[3] = 1;
        dp[4] = 2;
        dp[5] = 2;
        for (int i = 6; i < 101; i++) {
            dp[i] = dp[i - 1] + dp[i - 5];
        }
        
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            sb.append(dp[n]).append("\n");
        }
        
        System.out.print(sb);
    }
}