백준 2133, 2141

🧩 백준 2133 : 타일 채우기 

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

2133번: 타일 채우기

 

🧩 동적 계획법 문제

🧩 글로 쓰는것보다 그림이 더 이해가 잘 될 것 같아서 그림으로 그려봤다. 

🧩 참고로 가로 길이가 홀수인 경우는 0이다. 타일 2종류로 채울 수 있는 방법이 없음. 그러므로 DP 계산할 때는 짝수만 해주면 된다.  

 

 

🧩 아래는 DP[6]과 DP[4]인 경우이다. 모든 케이스를 다 그리진 않고, 왼쪽에 그려놓은 것 처럼 각 단계별로 추가되는 독립적인(?) 타일 조합만 그려놨다. 

🧩 앞단계의 모양을 조합해서 나올 수 없는 타일 조합이므로 얘는 추가로 +2를 해줄 것( 편의상 유니크 타일이라고 명칭)

🧩 그리고 그림에도 설명을 써놨지만, 이미 DP[4]에서 4칸 조합을 다 구해놨었다.  하지만 이 타일들 조합은 배치 순서가 바뀌면 다른 조합이므로 4칸짜리를 앞에 두고 뒤에 2칸짜리를 넣느냐, 아니면 2칸짜리를 앞에 두느냐가 다르다. 

그러므로 이 순서가 바뀐 걸 염두해두고 한번 더 [ 4칸짜리 유니크 타일 2개 X 나머지 2칸을 채우기 위한 DP[2] 값 ] 계산해준 뒤 더한다.

🧩 따라서 DP[6]= 33 + 6 + 2 = 41

 

 

🧩 DP [8]은 어떻게 구해지는가? 

🧩 DP [6] (6칸이 이미 지정되어 있을 때 ) X 나머지 2칸 채우는 방법 = DP[6] * DP[2] = 123

🧩 6칸짜리 유니크 타일 X DP[8-6] = 2 X DP[2] = 6 

🧩 4칸짜리 유니크 타일 X DP[8-4] = 4 X DP[4] = 22

🧩 8칸짜리 유니크 타일 2개 

🧩 123 + 6 + 22 + 2 = 153 

 

 

🧩 점화식

🧩 DP[N] = 가로 길이가 N인 사각형에 타일 채우는 경우의 수 

🧩 N이 홀수라면 : 0

 

🧩 N이 짝수라면 : DP[ N - 2 ] * DP[2](얘는 기본으로 들어감) + DP[ N - 4 ] * 2 + DP[ N - j ] * 2 + ... + 2  (j가 N보다 작다면 +2씩 증가시키는 방식)

 

* 사실 N=2인 케이스도 점화식 내에 넣어도 상관은 없지만 그냥 뺴놨다. 어쨌건 DP[0] = 1로 초기화만 잘 해놓으면 된다.  

* 배열을 선언하면 초기값이 다 0이므로 홀수 인덱스들은 딱히 계산하지 않음. 

 

 

🧩 전체 코드 

import java.util.*;
public class p2133 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] DP = new int[31];
        DP[0] = 1;
        DP[2] = 3;
        if (n <= 3) {
            System.out.println(DP[n]);
            return;
        }
        for (int i = 4; i <= n; i+=2) {
            DP[i] = DP[i-2] * DP[2] + 2;
            for (int j = 4; j < i; j+=2) {
                DP[i] += DP[i-j] * 2;
            }
        }

        System.out.println(DP[n]);
    }
}

 

---

🏣 백준 2141 : 우체국

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

2141번: 우체국

🏣 그리디 문제

🏣 거리를 다 계산해야 하는 줄 알았는데 그게 아니었다. 도무지 거리 안쓰고 어떻게 쓰는지 모르겠어서 서치를 해봄

🏣 근데 굉장히 단순한 로직이었다. 결국 각 사람들 간 거리의 합이 최소화되어야 하고, 우체국은 하나밖에 못 세우므로 사람들은 최대한 균등하게 나누어져 있으면 된다.

🏣 그래서 가장 왼쪽 마을부터 쭉 탐색하면서 현재 왼쪽에 거주하는 인원이 전체 인원의 절반이상이 되는 지점이 정답이다. 

 

 

 

🏣 전체 코드 

import java.io.*;
import java.util.*;
public class p2141 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long total = 0;
        Town [] village = new Town[n];
        StringTokenizer st;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            long location = Long.parseLong(st.nextToken());
            long people = Long.parseLong(st.nextToken());
            village[i] = new Town(location, people);
            total += people;
        }

        Arrays.sort(village, Comparator.comparingLong((o) -> o.location));
        long left = 0L;
        for (int i = 0; i < n; i++) {
            left += village[i].num;
            if ((total + 1) / 2 <= left) {
                System.out.println(village[i].location);
                break;
            }
        }

    }
    static class Town {
        long location;
        long num;
        public Town(long location, long num) {
            this.location = location;
            this.num = num;
        }
    }

}