<백준> 24.07.19에 푼 문제들

1. 삼각 그래프 (Silver 1)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/4883 삼각 그래프 at main · heesoo-park/ForCodeKata

제출 결과

---

뭔가 풀어봤던 유형인 거 같은데 잘 생각나지 않아서 시간이 많이 걸렸다.

그리고 왜 옆으로 가는 화살표가 있나 했는데 조건 중에 제곱해서 1000000보다 작다는 거에서 음수가 가능하기 때문이었다...!

그러면 옆으로 갔다가 가는게 더 최솟값이 나올 수 있다.

 

무조건 1층 중간값부터 시작하기 때문에 dp 배열 초기값은 왼쪽은 Integer.MAX_VALUE로, 가운데는 value 값으로, 오른쪽은 가운데 value + 오른쪽 value로 설정했다.

그리고 나서 다음 층 dp 값은 해당 위치로 올 수 있는 값들을 비교해서 최솟값을 구하여 채워갔다.

 

바텀업과 탑다운의 큰 차이점은 바텀업에서는 dp[i][1], dp[i][2], dp[i][3]을 반복문 안에서 한번에 구했지만 탑다운에서는 조건문으로 하나씩 구했다는 것이 있다.

 

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

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

public class Main {
    
    private static int[][] value;
    private static int[][] dp;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        
        int k = 0;
        while (true) {
            int n = Integer.parseInt(br.readLine());
            if (n == 0) break;
            
            k++;
            value = new int[n + 1][4];
            dp = new int[n + 1][4];
            
            for (int i = 1; i <= n; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 1; j < 4; j++) {
                    value[i][j] = Integer.parseInt(st.nextToken());
                    dp[i][j] = Integer.MAX_VALUE;
                }
            }
            
            dp[1][2] = value[1][2];
            dp[1][3] = value[1][2] + value[1][3];
            sb.append(k).append(". ").append(solve(n, 2)).append('\n');
        }
        
        System.out.print(sb);
    }
    
    static int solve(int n, int c) {
        if (n == 1 || dp[n][c] != Integer.MAX_VALUE) return dp[n][c];
        
        if (c == 1) {
            dp[n][1] = Math.min(solve(n - 1, 1), solve(n - 1, 2)) + value[n][1];
        } else if (c == 2) {
            dp[n][2] = Math.min(Math.min(solve(n - 1, 1), solve(n - 1, 2)), Math.min(solve(n - 1, 3), solve(n, 1))) + value[n][2];
        } else {
            dp[n][3] = Math.min(Math.min(solve(n - 1, 2), solve(n - 1, 3)), solve(n, 2)) + value[n][3];
        }
        
        return dp[n][c];
    }
}


// 바텀업 방식
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();
        StringTokenizer st;
        
        int k = 0;
        while (true) {
            int n = Integer.parseInt(br.readLine());
            if (n == 0) break;
            
            k++;
            int[][] value = new int[n + 1][4];
            int[][] dp = new int[n + 1][4];
            
            for (int i = 1; i <= n; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 1; j < 4; j++) {
                    value[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            
            dp[1][1] = 10000001;
            dp[1][2] = value[1][2];
            dp[1][3] = value[1][2] + value[1][3];
            for (int i = 2; i <= n; i++) {
                dp[i][1] = Math.min(dp[i - 1][1], dp[i - 1][2]) + value[i][1];
                dp[i][2] = Math.min(Math.min(dp[i - 1][1], dp[i - 1][2]), Math.min(dp[i - 1][3], dp[i][1])) + value[i][2];
                dp[i][3] = Math.min(Math.min(dp[i - 1][2], dp[i - 1][3]), dp[i][2]) + value[i][3];
            }
            
            sb.append(k).append(". ").append(dp[n][2]).append('\n');
        }
        
        System.out.print(sb);
    }
}

 

2. 구간 합 구하기 5 (Silver 1)

[백준]

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

[깃허브]

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

제출 결과

---

이 문제는 불현듯 떠오른 사각형 4개 덕분에 금방 풀 수 있었다.

누적합을 구할 때와 dp 배열 값 채울 때 모두 사용했다.

큰 사각형, 작은 사각형, 긴 사각형 2개... 설명을 이렇게밖에 못하겠네

중첩되는 부분을 한번 빼주는 방식이다..!!

 

시간이 왜 이리 오래 걸렸나 싶다...

 

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

// 바텀업 방식
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[][] table = 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 <= n; j++) {
                table[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        dp[1][1] = table[1][1];
        for (int i = 2; i <= n; i++) {
            dp[1][i] = dp[1][i - 1] + table[1][i];
            dp[i][1] = dp[i - 1][1] + table[i][1]; 
        }
        
        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= n; j++) {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + table[i][j];
            }
        }
        
        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());
            
            bw.write(dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1] + "\n");
        }
        
        bw.flush();
        bw.close();
    }
}