[프로그래머스]Level.2 멀쩡한 사각형

 

코딩테스트 연습 - 멀쩡한 사각형

 

문제설명

 

입출력예

 

using namespace std;

long long gcd(long long a, long long b){
   return b>0?gcd(b,a%b):a;
}


long long solution( int w,int h) {
    long long answer = 1;
    long long num=gcd(w,h);
    long long square=(long long)w*h;
    answer=square-(w+h-num);
    return answer;
}

 

하 코드는 이렇게 간단하지만 ㅠㅠㅠ이 문제를 푸는건 생각보다 간단하지 않았다.

사각형이 잘리는 규칙을 알려면 최대공약수의 개념이 필요하다.

나는 처음 이 문제를 보고 풀기 쉽겠는데 생각하고 코드를 쭉쭉 써내려갔다

테스트케이스도 추가해보고 오 되는군 ...만족하며 제출눌렀는데 실패 ㅎㅎ

다른 테스트 케이스도 고려해보니 내 풀이가 틀렸다는 걸 알게됐다.

 

최대 공약수만큼 패턴이 반복

두시간 정도 고민하다가 계속 생각이 제자리에 머물러 있는 것 같아서 다른 사람들의 풀이를 보고 도움을 받았다.

제일 처음에는 최대공약수?라는 개념을 보고 이 문제랑 무슨 관련이지 싶었는데....위에 그림을 보면 8과 12의 최대 공약수 4를 기준으로 사각형이 잘려나가는 규칙이 반복되는 것을 알 수 있다.대각선은 곧 기울기이기 때문에 12 와 8의 최대 공약수를 기준으로 기울기가 반복되어..패턴이 반복된다고도 할수 있다.

 

단위 사각형에서 잘리는 규칙

패턴이 최대공약수만큼 반복되는 것은 이제 알았을 것이다.그 다음 생각해야 할것은 패턴이 반복되는 하나의 단위 사각형에서 사각형이 잘리는 규칙이다.여기서 최단 거리의 개념을 잠시 떠올려보자 !!대각선은 가로길이와 세로길이의 최단거리다 ! 결국 가로길이만큼 세로길이만큼 이동을 해야한다는 뜻이다. 사각형을 가로1씩 세로1씩 이동했을때 잘려지는 것을 관찰해보자

 

 

초록색은 가로방향진행시 노란색은 세로방향 진행시 잘려지는 칸을 표시했다.

첫 한칸은 세로 방향으로 진행하든 가로 방향으로 진행하든 잘려진다

두번째로 세로방향으로 진행시 (2,1)칸이 칠해진다.

세번째로 가로방향으로 진행시 (2,2)칸이 칠해진다.

세번재로 세로방향으로 진행시 (3,2)칸이 칠해진다.

 

결국 칸은 세로길이(/gcd)+가로길이(/gcd)-1(첫 한칸! ==어느방향으로 진행하든 겹쳐지는 한칸)만큼 칠해지게 된다.잘리는 칸은 gcd만큼 반복되기 떄문에 결국 전체 사각형 내에서 잘리는 사각형의 개수는 세로길이+가로길이-gcd라고 할수있다.

 

이 문제에서 주어지는 높이와 넓이는 매우 큰 수 이기 떄문에 오버플로우를 조심해주지 않으면 테스트케이스 12번부터 쭉~~틀리게 된다.