백준 23971번 ZOAC 4(JAVA)

23971번: ZOAC 4

 

풀이코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        int H, W, N, M = 0;
        int x, y = 0;
        
        H = Integer.parseInt(st.nextToken()); // 세로 칸수
        W = Integer.parseInt(st.nextToken()); // 가로 칸수
        N = Integer.parseInt(st.nextToken()); // 세로로 비우고 앉아야 하는 칸수
        M = Integer.parseInt(st.nextToken()); // 가로로 비우고 앉아야 하는 칸수
        
        x = H / (N + 1);
        y = W / (M + 1);
        
        if (H % (N + 1) != 0) {
            x += 1;
        }
        
        if (W % (M + 1) != 0) {
            y += 1;
        }
        
        System.out.println(x * y);

    }
}

 

풀이과정

문제를 처음 보고 이건 사람을 앉힌다고 생각하기 보다는 영역을 나누는 문제에 가깝다고 생각을 했다.

예를 들어 세로 칸 수 H가 5, 가로 칸 수 W가 5, 가로 세로 띄워서 앉아야 하는 칸 수 N, W가 1이라고 했을 때 2 x 2 사각형을 5 x 5 사각형에 얼마나 많이 배치시킬 수 있는지 계산하는 것이다.

위 예시로 계속 설명을 하자면 어떤 사람이 특정 칸에 앉아 있을 때 이 사람이 차지하는 가로 칸수는 2칸이다.

자기가 앉아 있는 칸 1에 띄워 앉아야 하는 칸 1를 더해주기 때문이다.

전체 가로 칸수 5를 2로 나누면 2 x 2 사각형이 2번 들어갈 수 있고(영역 1, 영역 2), 남는 1칸에 2 x 1 사각형이 1번 들어갈 수 있다(영역 3). 세로도 마찬가지로 계산해주면 가로 세로 모두 3개의 영역이 포함될 수 있다. 

이를 수식으로 나타내면 아래와 같고, 이를 코드로 나타내주면 된다!

---

1. 가로에 들어갈 수 있는 칸 수 = 전체 가로 칸 수 / 한 사람이 차지하는 온전한 사각형 수 + 자투리 칸에 끼워넣을 수 있는 사각형 수

2. 세로에 들어갈 수 있는 칸 수 = 전체  세로 칸 수 / 한 사람이 차지하는 온전한 사각형 수 + 자투리 칸에 끼워넣을 수 있는 사각형 수 

3. 정답 = 가로에 들어갈 수 있는 칸 수 * 세로에 들어갈 수 있는 칸 수  

---

이때 주의할 점은 자투리 칸에 끼워넣을 수 있는 사각형 수를 계산하는 부분이다.

나같은 경우는 나머지가 있으면 이를 더해주면 되겠다 싶어서 W % (M + 1) 로 계산했다가 수많은 오답을 생성했다 ㅎㅎ...

다시 생각해보니 자투리 공간에는 최대 1개만 추가로 들어갈 수 있으므로, W / (M + 1) 을 했을 때 나머지가 생기는 경우에만 1을 더해주는 방식으로 변경했다.

그리고 다시 코드를 채점해보니 정답 !