<백준> 24.07.12에 푼 문제들

1. RGB거리 (Silver 1)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/1149 RGB거리 at main · heesoo-park/ForCodeKata

제출 결과

---

2차원 배열 dp가 등장했다. 당황했다.

하지만 바텀업 방식, 반복문을 사용하는 방식으로 해결했다.

탐다운 방식, 재귀문을 사용하는 방식도 해보려고 노력했지만 잘 되지 않아 다른 사람의 풀이를 참고해서 해봤다.

비슷한 듯 달라서 아직은 헷갈린다.

앞으로 Sliver 1 문제는 두 가지 방식을 다 시도해봐야겠다.

 

걸린 시간은 신기하게 동일했다.

 

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

// 탑다운 방식
import java.io.*;
import java.util.*;

public class Main {
    
    private static int[][] cost = new int[1001][3];
    private static int[][] dp = new int[1001][3];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int n = Integer.parseInt(br.readLine());
        
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());            
            for (int j = 0; j < 3; j++) {
                cost[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        dp[1][0] = cost[1][0];
        dp[1][1] = cost[1][1];
        dp[1][2] = cost[1][2];
        
        System.out.print(Math.min(paintHouse(n, 0), Math.min(paintHouse(n, 1), paintHouse(n, 2))));
    }
    
    static int paintHouse(int n, int color) {
        if (dp[n][color] == 0) {
            if (color == 0) {
                dp[n][color] = Math.min(paintHouse(n - 1, 1), paintHouse(n - 1, 2)) + cost[n][color];
            } else if (color == 1) {
                dp[n][color] = Math.min(paintHouse(n - 1, 0), paintHouse(n - 1, 2)) + cost[n][color];
            } else {
                dp[n][color] = Math.min(paintHouse(n - 1, 0), paintHouse(n - 1, 1)) + cost[n][color];
            }
        }
        
        return dp[n][color];
    }
}


// 바텀업 방식
import java.io.*;
import java.util.*;

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

 

2. 1로 만들기 2 (Silver 1)

[백준]

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

[깃허브]

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

제출 결과

---

재귀를 하기에는 너무 숫자가 컸다...

바텀업만 진행했다.

1로 만들기 문제에서 추가된 것은 경로 출력이었다.

어떻게 할까 하다가 Stack을 써볼까 하고 했는데 원하는대로 결과가 나오지 않았다.

아마 알고리즘을 잘못 구현한 거 같다.

 

그래서 좀 다른 방식을 찾아보는데 dp 배열 채울 때와 역순으로 돌며 경로를 구하는 방법이 있었다.

dp 배열을 채울 때는 연산 3, 2, 1 순으로 체크를 했는데 경로를 1, 2, 3 순으로 체크했다. 

물론 전자는 다 if 문이고 후자는 if - else 문이다.

전자는 모든 경우를 다 체크해야하기 때문이고 후자는 가장 먼저 나오는 케이스만 찾으면 되기 때문이다.

이 방식은 까먹지 않고 잘 기억해놔야겠다.

 

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

// 바텀업 방식
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[] dp = new int[n + 1];        
        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);
            }
        }
        
        sb.append(dp[n]).append("\n");
        sb.append(n).append(' ');
        while (n > 1) {
            if (n % 3 == 0 && dp[n] == dp[n / 3] + 1) {
                sb.append(n / 3).append(' ');
                n /= 3;
            } else if (n % 2 == 0 && dp[n] == dp[n / 2] + 1) {
                sb.append(n / 2).append(' ');
                n /= 2;
            } else {
                sb.append(n - 1).append(' ');
                n -= 1;
            }
        }
        
        System.out.print(sb);
    }
}

 

3. 정수 삼각형 (Silver 1)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/1932 정수 삼각형 at main · heesoo-park/ForCodeKata

제출 결과

---

아래에서 위로 삼각형을 점점 좁혀가는 방식은 바텀업, 위에서 아래로 삼각형을 점점 넓혀가는 방식은 탑다운

이번에는 탑다운 방식이 조금 더 빨랐다.

탑다운에서는 가장 아래에 도달했을 때 그 값을 가지고 와서 비교하는 것을 재귀문으로 구현했고 바텀업에서는 이중 for문으로 아래부터 차근차근 구현했다.

 

탑다운 방식이 어려운 문제에서는 많이 사용된다고 들었던 거 같은데 익숙해질 수 있을지 모르겠다...ㅎㅎ

 

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

// 탑다운 방식
import java.io.*;
import java.util.*;

public class Main {
    
    private static int[][] triangle;
    private static int[][] dp;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int n = Integer.parseInt(br.readLine());
        triangle = new int[n + 1][n + 1];
        dp = new int[n + 1][n + 1];
        
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= i; j++) {
                triangle[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        for (int i = 1; i <= n; i++) {
            dp[n][i] = triangle[n][i];
        }
        
        System.out.print(findMaxSum(n, 1, 1));
    }
    
    static int findMaxSum(int n, int depth, int idx) {
        if (depth == n) return dp[depth][idx];
        
        if (dp[depth][idx] == 0) {
            dp[depth][idx] = Math.max(findMaxSum(n, depth + 1, idx), findMaxSum(n, depth + 1, idx + 1)) + triangle[depth][idx];
        }
        
        return dp[depth][idx];
    }
}


// 바텀업 방식
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 n = Integer.parseInt(br.readLine());
        int[][] triangle = new int[n + 1][n + 1];
        int[][] dp = new int[n + 1][n + 1];
        
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= i; j++) {
                triangle[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        for (int i = 1; i <= n; i++) {
            dp[n][i] = triangle[n][i];
        }
        
        for (int i = n - 1; i > 0; i--) {
            for (int j = 1; j <= i; j++) {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];
            }
        }
        
        System.out.print(dp[1][1]);
    }
}