아래의 두 글을 참고 하였습니다

https://school.programmers.co.kr/questions/45467
https://school.programmers.co.kr/questions/48902

---

설명

그림 없이는 이해가 힘들기 때문에 문제의 8x12 가 화면에서 보인다고 가정 하고 설명 하겠습니다
그림을 보게되면 특이한 부분을 확인 할 수 있습니다

◻◼
◻◻ (회색: 제외 되어야 하는 블록)
◼◻ (검은색: 사용할 수 있는 블록)

이렇게 생긴 형태가 4번 반복되는 것을 볼 수 있어요. (이제 이것을 ‘N기호’ 라고 명명하고 설명 하겠습니다)

이 말은 즉, [w:2, h:3] 이 되든 [w:4, h:6] 이 되든 저 형태를 계산하는 공식과 반복 횟수를 구하는 공식을 찾으면 문제를 풀 수 있다는 말이 됩니다.

이해의 편의성을 위해 저 회색 블록의 개수를 구하는 방법을 먼저 설명합니다

1 ) 사용하지 못하는 블록 갯수 구하기

‘N기호’ 는 특징을 가지고 있습니다

바로 w + h - 1 을 하게 되면 사용하지 못하는 블록의 수가 나온다는 것입니다
(한번 그려서 확인 해 보시는 것을 추천드립니다.)

간단한 예시를 보겠습니다

다음은 w:8,h:5 의 종이 입니다

◻◻◼◼◼◼◼◼
◼◻◻◻◼◼◼◼
◼◼◼◻◻◼◼◼
◼◼◼◼◻◻◻◼(회색: 제외 되어야 하는 블록)
◼◼◼◼◼◼◻◻(검은색: 사용할 수 있는 블록)

여기서 위의 공식을 대입 해 보겠습니다

w + h - 1 == 8 + 5 - 1

결과는 12 가 되며 회색 블록의 개수도 정확히 12개 입니다.
(왜 그런지는 증명하기 어렵습니다. 21 개의 경우를 그려서 확인 해 본 결과 맞는다는 판단을 내려서 공식을 fix 했습니다.)

하지만 예외 케이스가 존재 합니다. 그 예외 케이스는 바로 w:8,h:12 의 경우입니다

예외 케이스는 특징을 가지고 있는데, 특정한 패턴이 반복해서 등장한다는 것 입니다

그 경우를 제외 한다면 반복 횟수가 없는 경우는 해당 공식을 통해 모든 해를 구할 수 있습니다

이 해가 적용 되는 w, h 값들을 공유합니다.

• w:5,h:8 ⇒ 5+8-1 = 12
• w:8,h:3 ⇒ 8+3-1 = 11
• w:5,h:7 ⇒ 5+7-1 = 11
• w:4,h:7 ⇒ 4+7-1 = 10
• w:3,h:7 ⇒ 3+7-1 = 9

위 공식을 사용하여 ‘제외되는 블록의 개수’ 를 구할 수 있는 위의 경우들은 특징을 한가지 가지고 있습니다

바로 반복되지 않는다는 점 입니다

그렇다면 이렇게 생각 해 볼 수 있습니다.

n 번 반복 된다면 정확히 저 공식의 결과 * n 이 됩니다.

만일 w:5,h:8 의 값이 두배가 되어 w:10,h:16 이 되면 정확히 저 공식의 결과도 두배인 24 가 된다는 이야기 입니다

그럼 여기서 반복을 구하면 됩니다

2) 반복 횟수 구하기

반복 횟수는 ‘최소 반복 블록 단위’로 구할 수 있습니다.

위의 ‘N기호’를 다시 가져오겠습니다.

◻◼
◻◻ (회색: 제외 되어야 하는 블록)
◼◻ (검은색: 사용할 수 있는 블록)

이것은 w:8,h:12 의 최소 반복 단위 입니다. 사이즈는 w:2,h:3 이 됩니다

w:2 는 반복 되어야 하는 너비 이며 h:3 은 반복 되어야 하는 높이 입니다

w:2,h:3 에게 각각 4를 곱하면 w:8,h:12 가 됩니다.

그럼 몇 번 반복되어야 하는지 어떻게 알 수 있을까요

w 와 h 의 숫자가 공통적으로 나누어 지는 수를 구하면 됩니다. 그래서 다른 글 들에서도 최대공약수가 나오게 되는겁니다. (최대공약수는 호제법으로 구할 수 있습니다. 호제법은 Euclidean algorithm 이라고도 합니다)

좀 더 쉽게 이야기 하면 이렇습니다

8,12 의 최대공약수는 4 입니다

8 과 12 를 최대공약수인 4로 나눕니다

그럼 결과는 2, 3 이 됩니다

위에서 확인 한 ‘사이즈’ 와 같은 수가 됩니다

결과적으로 최대공약수는 패턴의 반복 횟수가 됩니다.

3) 결과 구하기

1 에서는 제외 블록 수(사용하지 못하는 블록의 갯수)를 구했습니다

2 에서는 반복 횟수를 구했습니다

그럼 [전체블록수] - [제외블록수] * [반복횟수] 의 결과가 해답이 됩니다

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public long solution(int w, int h) {
        long allBlockCount = (long)w*h;

        long repetitionCount = euclideanAlgorithm(w, h);

        long widthRepeatSize = (long)w / repetitionCount;
        long heightRepeatSize = (long)h / repetitionCount;

        long cutBlockCount = widthRepeatSize + heightRepeatSize - 1;

        return allBlockCount - cutBlockCount * repetitionCount;
    }

    private int euclideanAlgorithm(int a, int b) {
        if (b == 0){
            return a;
        }
        return euclideanAlgorithm(b, a % b);
    }
}