<백준> 24.07.04에 푼 문제들

1. 2xn 타일링 (Silver 3)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/11726 2×n 타일링 at main · heesoo-park/ForCodeKata

제출 결과

---

전에 풀었던 1, 2, 3 더하기같은 문제라고 생각했다.

n이 주어졌을 때 앞에가 2x1인 경우와 2x2인 경우로 나눠서 생각했을 때 그에 해당하는 값은 n - 1일 때의 값과 n - 2일 때의 값이 될 것이다.

한 칸을 고정하고 나머지로 만들 수 있는 경우의 수를 만드는 것이고 두 칸을 고정하고 나머지로 만들 수 있는 경우의 수를 만드는 것이기 때문이다.

1과 2만 하는 것은 딱 직관적으로 값을 구할 수 있으면서 문제에서 1x2, 2x1로 채운다는 것에서 그래야겠다는 생각이 들었기 때문이다.

dp[i] = dp[i - 2] + dp[i - 1] (i > 2) 이라는 점화식이 나온다.

 

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

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

public class Main {
    
    static long[] dp = new long[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] = 1L;
        dp[2] = 2L;
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 2] + dp[i - 1]) % 10007;
        }
        
        System.out.print(dp[n]);
    }
}

 

2. 구간 합 구하기 4 (Silver 3)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/11659 구간 합 구하기 4 at main · heesoo-park/ForCodeKata

제출 결과

---

누적합을 구하서 dp 배열에 넣고 부분합을 구하는 것으로 해결했다.

누적합에서 부분합을 구할 때는 left 값에 -1해줘야한다.

 

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

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        int[] dp = new int[n + 1];
        int[] list = new int[n + 1];
        
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            list[i] = Integer.parseInt(st.nextToken());
        }
        
        dp[1] = list[1];
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + list[i];
        }
        
        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());
            
            int sum = dp[right] - dp[left - 1];
            bw.write(sum + "\n");
        }
        
        bw.flush();
        bw.close();
    }
}