멀쩡한 사각형
문제 설명
- w*h 직사각형을 대각선으로 잘랐을 때 잘리는 정사각형(1x1)을 제외한 정사각형 개수를 반환한다.
ex) 8*12 직사각형으로 96개의 정사각형을 만들 수 있다. 이때 잘리는 정사각형은 16개이다. 96-16 = 80 반환.
시행착오 및 문제 풀이
오답 풀이
그림을 슥슥 그려봤을 때 규칙이 보였다.
nxn이면 n개의 사각형이 잘리고, nxm이면 n과 m중 더 작은 값에서 2를 곱한 것이 잘린 사각형의 개수였다. (그런 줄 알았다.)
왜냐면 내가 그린 사각형들은 2x2, 3x3, 2x3, 3x4 였기 때문에....
그래서 아래와 같은 코드가 나왔고 너무 화나게도 예제 코드는 통과했다. 희망고문이다.
오답 코드
//n*n을 대각선으로 그으면 n개 잘림
//n*m을 대각선으로 그으면 n과 m 둘 중 작은 수에 *2개 잘림
import java.util.*;
class Solution {
public long solution(int w, int h) {
long answer = 0;
int total = w*h;
if(w==h) {
answer = total - w;
}
else {
int min = Math.min(w,h);
answer = total - (min*2);
}
return answer;
}
}16.7.. 나의 풀이에 확신을 가졌던 게 창피해지는 순간이였다.
오답 이유
내 풀이대로라면 3x4의 잘린 사각형 개수는 6이고, 3x5의 잘린 사각형 개수도 6이고, 3x9의 잘린 사각형 개수도 6이다. ㅋ 그냥 틀렸다. 왜 거기까지 생각을 못했즵
뭔가 최대공약수를 사용할 것 같은 느낌에 이것 저것 대입해보다가 규칙을 찾았다!!!
정답 풀이
-
잘린 사각형 갯수 공식: w+h-(w,h의 최대 공약수)
ex) 8과 12일 때, 8과 12의 최대공약수는 4
8+12-4 = 16
3과 4일 때, 3과 4의 최대공약수는 1
3+4-1 = 6
3과 3일 때, 3과 3의 최대공약수는 3
3+3-3 = 3 -
전체 사각형 개수(w*h) - 잘린 사각형 개수 반환
오답 코드
//잘린 사각형 개수 공식: w+h-(w,h의 최대공약수)
import java.util.*;
class Solution {
public long solution(int w, int h) {
long answer = 0;
int n = w+h-gcd(w,h);
answer = w*h-n;
return answer;
}
public int gcd(int a, int b) {
if(b == 0) {
return a;
}
return gcd(b, a%b);
}
}그렇게 풀었는데도 틀렸다.
사실 풀면서도 '아.. answer이 long이네.. 형변환 필요할 것 같은데.. 아 조건도 1억이네.....' 하면서 풀긴 했음.
정답 코드
//잘린 사각형 개수 공식: w+h-(w,h의 최대공약수)
import java.util.*;
class Solution {
public long solution(int w, int h) {
long answer = 0;
long total = (long)w*h;
long n = (long)w+h-gcd(w,h);
answer = total - n;
return answer;
}
public long gcd(int a, int b) {
if(b == 0) {
return a;
}
return gcd(b, a%b);
}
}int형들을 다 long형으로 변환해주었다.
정답!!!!
푸는 원리를 알면 구현은 어렵지 않았던 문제같다.
근데 최대공약수로 공식 알아내는 게 좀 어려울듯하다.
나는 이것~ 저것~ 다 집어넣어보다가 우연찮게 걸린거여서... 럭키비키
