쉬운 문제라도 문제를 푸는 방법은 다양합니다.
더 명확하고 깔끔한 문제 해결 방법을 아신다면 자유롭게 말씀해주세요.
프로그래머스 120922 종이 자르기
프로그래머스 저작권을 침해하지 않기 위해
문제 보시고 싶으시면 버튼을 눌러주세요.
답변 형식
가로 길이와 세로길이 M, N을 받아 한 변의 길이가 1인 정사각형을 만들기 위한 최소 가위질 횟수를 구하면 됩니다.
풀이 조건
– 가위질을 할 때 ‘종이를 겹쳐서 자를 수 없다’고 했습니다.
-> 가위질 횟수에 관한 식은 한 개 입니다.
– 처음 가위질을 통해 한 변의 길이가 1인 정사각형을 만들고. 두 번째 가위질로 모든 변의 길이가 1인 정사각형을 만듭니다.
– 이 문제는 수학문제와 같습니다.
문제 해설
가위질 횟수의 총 합은
1. (M-1) + M*(N-1)
2. (N-1) + N*(M-1)
처음 방향이 M이면 1번, N이면 2번 함수입니다.
식을 전개한다면
1. M-1+MN-M
2. N-1+MN-N
으로 나옵니다.
결국 1번이나 2번이나 결과는 MN-1 로 같습니다.
JAVA 긴 정답
class Solution {
public int solution(int M, int N) {
int max = Math.max(M, N);
int min = Math.min(M, N);
if(max==1) return 0;
else if(min==1) return max–1;
else return (max–1)+(max*(min–1));
}
}
JAVA 짧은 정답
class Solution {
public int solution(int M, int N) {
return M*N-1;
}
}
Python3 긴 정답
def solution(M, N):
nowmax = max(M,N)
nowmin = min(M,N)
return (nowmax–1)+(nowmax*(nowmin–1))
Python3 짧은 정답
def solution(M, N):
return M*N–1