<백준> 24.07.11에 푼 문제들

1. 가장 큰 증가하는 부분 수열 (Silver 2)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/11055 가장 큰 증가하는 부분 수열 at main · heesoo-park/ForCodeKata

제출 결과

---

dp 배열 초기값과 2중 for문, 현재 위치 기준으로 왼쪽 편 숫자들 체크하는 방식 생각나지 않았다...

또한 같은 숫자들이 나올 때 틀리는 문제가 있었는데 continue를 사용하면서 두번째 for문 안에 있는 max = Math.max(max, dp[i]);가 실행되지 않아서 생기는 문제였다.

이를 해결하기 위해 두번째 for문이 실행되기 전에 미리 한번 max = Math.max(max, dp[i]);을 실행시켰다.

 

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

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 = Integer.MIN_VALUE;
                
        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());
            dp[i] = nums[i];
        }
        
        for (int i = 1; i <=n; i++) {
            max = Math.max(max, dp[i]);
            
            for (int j = 1; j < i; j++) {
                if (nums[j] >= nums[i]) continue;
                if (dp[j] + nums[i] <= dp[i]) continue;
                
                dp[i] = dp[j] + nums[i];
                max = Math.max(max, dp[i]);
            }
        }
        
        System.out.print(max);
    }
}

 

2. 가장 긴 증가하는 부분 수열 (Silver 2)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/11053 가장 긴 증가하는 부분 수열 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));
        StringTokenizer st;
        int max = 0;
        
        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());
            dp[i] = 1;
        }
        
        for (int i = 1; i <= n; i++) {
            max = Math.max(max, dp[i]);
            
            for (int j = 1; j <= i; j++) {
                if (nums[j] >= nums[i]) continue;
                if (dp[j] + 1 <= dp[i]) continue;

                dp[i] = dp[j] + 1;
                max = Math.max(max, dp[i]);
            }
        }
        
        System.out.print(max);
    }
}

 

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

[백준]

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

[깃허브]

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

제출 결과

---

숫자의 범위만 커진 1, 2, 3 더하기 문제였다.

dp 배열 타입을 long으로 잡으니까 쉽게 해결됐다.

 

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

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

public class Main {
    
    private static long[] dp = new long[1000001];
    
    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] = 2;
        dp[3] = 4;
        for (int i = 4; i < 1000001; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 1000000009;
        }
        
        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);
    }
}

 

4. 제곱수의 합 (Silver 2)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/1699 제곱수의 합 at main · heesoo-park/ForCodeKata

제출 결과

---

DP 문제는 역시 그려봐야지 좀더 이해가 쉽다

보고는 1, 2, 3 더하기 문제처럼 앞에를 고정하는 식으로 되지 않을까 했고 맨 앞을 특정 제곱수로 했을 때 나오는 값의 최소를 계속 업데이트하는 식으로 해결했다.

반복문의 조건을 이렇게 활용할 수 있었다는 것을 까먹고 있었다.

 

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

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

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