<div id="readability-page-1" class="page"><div><h2 id="-링크">🔗 링크</h2>

<h2 id="-문제">🔳 문제</h2>
가로길이 W, 세로 길이가 H인 직사각형에서 대각선 꼭지점 2개를 잇는 방향으로 선을 그었을 때,
<div>선이 그어지지 않은 정사각형의 갯수를 구해야한다.</div>
<h2 id="-예제로-문제-파악하기">👀 예제로 문제 파악하기</h2>
입력 : <code>w</code> 8, <code>h</code> 12
<img src="https://media.vlpt.us/images/ajufresh/post/3c53d3b6-89f6-4837-9ec9-7eca4293c953/image.png">
가로가 8, 세로가 12인 직사각형이 있고, 각 대각선 꼭지점에서 선을 그으면
위 사진처럼 잘리게 된다.
<img src="https://media.vlpt.us/images/ajufresh/post/3d93e2b4-acc4-4cab-9be5-30314de0a06a/image.png">
그리고 빨간색 펜으로 쳐져있는 것 처럼 반복되는 것을 확인할 수 있다.
이때 반복이 끝나는 지점의 좌표를 구하면 아래와 같이 나오게 된다.
[2, 3] / [4, 6] / [6, 9] / [8, 12]
x(총 길이 : 8)는 2씩, y(총 길이 : 12)는 3씩 증가하는 패턴을 찾을 수 있는데,
8 → 2
12 → 3으로 되는 조건을 찾아보니, 둘 다 4로 나눈 값인 것을 발견할 수 있었다.

따라서 패턴 직사각형의 크기는 2(w/최대공약수)*3(h/최대공약수)가 된다.
그리고 패턴 직사각형에서 사용하지 못하는 정사각형을 빼야하는데,
이때 사용하지 못하는 정사각형을 구하기 위해서는
총 정사각형 갯수 - (가로 길이 + 세로길이 - 1)이 된다.
이 공식이 나온 이유는 아래와 같다.
<img src="https://media.vlpt.us/images/ajufresh/post/0d79f63b-07bf-46cd-95c2-fc1e0fb06959/image.png">
패턴 직사각형이 다음 꼭짓점으로 도달하기 위해서는 가로 길이, 세로 길이만큼 움직여야하는데,
가로 길이, 세로 길이 중에 겹치는 부분(파란색 부분) 이 있기 때문에 1을 빼는 것이다.
그러면 한 패턴당 사용하지 못하는 정사각형의 갯수를 구했으니,
이 패턴이 몇 번 반복하는지 알아야하는데, 이 패턴은 **최대 공약수(4)**만큼 반복했다.

(전체 크기) - (한 패턴 직사각형 당 사용하지 못하는 정사각형 크기 * 반복횟수)
<code>(w * h) - (((w / 최대공약수) + (h / 최대공약수) - 1) * 최대공약수)</code>
<div>우연의 일치인가? 싶어서 다른 예제를 만들어보았다.</div>
입력 : <code>w</code> 6, <code>h</code> 9
<img src="https://media.vlpt.us/images/ajufresh/post/5ad91f42-c253-410e-b51d-ec7eb80f2215/image.png">
6과 9의 최대 공약수는 3이고,
패턴은 최대공약수만큼 반복했다.
따라서 공식에 그대로 대입해보면
<div><code>(6 * 9) - ((6 / 3) + (9 / 3) - 1) * 3 = 54 - 12</code> = 42로, 정답이 제대로 나온다.</div>
<h2 id="-알고리즘-풀이-순서">😮 알고리즘 풀이 순서</h2>
<ol>
<li>w와 h의 최대 공약수(gcd)를 구한다.</li>
<li><code>(w * h) - (((w / gcd) + (h / gcd) - 1) * gcd)</code>를 리턴한다.<ul>
<li>단, w와 h는 각각 1억까지 가능하기 때문에 계산 과정에서 long 타입으로 형변환을 해준다.</li>
</ul> </li>
</ol>
<h2 id="-코드">👨‍💻 코드</h2>
<pre><code>public class Solution {
 public long solution(int w, int h) {
 int gcd = BigInteger.valueOf(w).gcd(BigInteger.valueOf(h)).intValue();
 return ((long) w * (long) h) - ((((long) w / gcd) + ((long) h / gcd) - 1) * gcd);
 }

 @Test
 public void 정답() {
 Assert.assertEquals(80, solution(8, 12));
 Assert.assertEquals(80, solution(12, 8));
 Assert.assertEquals(12, solution(4, 4));
 }
}</code></pre></div></div>

ajufresh.log

🔗 링크
https://programmers.co.kr/learn/courses/30/lessons/62048
🔳 문제
가로길이 W, 세로 길이가 H인 직사각형에서 대각선 꼭지점 2개를 잇는 방향으로 선을 그었을 때,
선이 그어지지 않은 정사각형의 갯수를 구해야한다.
👀 예제로 문제 파악하기
입력 : w 8, h 12
가로가 8, 세로가 12인 직사각형이 있고, 각 대각선 꼭지점에서 선을 그으면
위 사진처럼 잘리게 된다.
그리고 빨간색 펜으로 쳐져있는 것 처럼 반복되는 것을 확인할 수 있다.
이때 반복이 끝나는 지점의 좌표를 구하면 아래와 같이 나오게 된다.
[2, 3] / [4, 6] / [6, 9] / [8, 12]
x(총 길이 : 8)는 2씩, y(총 길이 : 12)는 3씩 증가하는 패턴을 찾을 수 있는데,
8 → 2
12 → 3으로 되는 조건을 찾아보니, 둘 다 4로 나눈 값인 것을 발견할 수 있었다.
그리고 4는 8과 12의 최대 공약수였다.
따라서 패턴 직사각형의 크기는 2(w/최대공약수)*3(h/최대공약수)가 된다.
그리고 패턴 직사각형에서 사용하지 못하는 정사각형을 빼야하는데,
이때 사용하지 못하는 정사각형을 구하기 위해서는
총 정사각형 갯수 - (가로 길이 + 세로길이 - 1)이 된다.
이 공식이 나온 이유는 아래와 같다.
패턴 직사각형이 다음 꼭짓점으로 도달하기 위해서는 가로 길이, 세로 길이만큼 움직여야하는데,
가로 길이, 세로 길이 중에 겹치는 부분(파란색 부분) 이 있기 때문에 1을 빼는 것이다.
 그러면 한 패턴당 사용하지 못하는 정사각형의 갯수를 구했으니,
이 패턴이 몇 번 반복하는지 알아야하는데, 이 패턴은 최대 공약수(4)만큼 반복했다.
따라서 나온 공식은 이랬다.
(전체 크기) - (한 패턴 직사각형 당 사용하지 못하는 정사각형 크기 * 반복횟수)
(w * h) - (((w / 최대공약수) + (h / 최대공약수) - 1) * 최대공약수)
우연의 일치인가? 싶어서 다른 예제를 만들어보았다.
입력 : w 6, h 9
6과 9의 최대 공약수는 3이고,
패턴은 최대공약수만큼 반복했다.
따라서 공식에 그대로 대입해보면
(6 * 9) - ((6 / 3) + (9 / 3) - 1) * 3 = 54 - 12 = 42로, 정답이 제대로 나온다.
😮 알고리즘 풀이 순서
w와 h의 최대 공약수(gcd)를 구한다.
(w * h) - (((w / gcd) + (h / gcd) - 1) * gcd)를 리턴한다.
단, w와 h는 각각 1억까지 가능하기 때문에 계산 과정에서 long 타입으로 형변환을 해준다.
👨‍💻 코드
public class Solution {
  public long solution(int w, int h) {
    int gcd = BigInteger.valueOf(w).gcd(BigInteger.valueOf(h)).intValue();
    return ((long) w * (long) h) - ((((long) w / gcd) + ((long) h / gcd) - 1) * gcd);
  }
  @Test
  public void 정답() {
    Assert.assertEquals(80, solution(8, 12));
    Assert.assertEquals(80, solution(12, 8));
    Assert.assertEquals(12, solution(4, 4));
  }
}

[프로그래머스] 멀쩡한 사각형 문제풀이 (Java)

댓글