[코딩 테스트 연습 입문] 종이 자르기
문제
머쓱이는 큰 종이를 1 x 1 크기로 자르려고 합니다. 예를 들어 2 x 2 크기의 종이를 1 x 1 크기로 자르려면 최소 가위질 세 번이 필요합니다.
정수 M, N이 매개변수로 주어질 때, M x N 크기의 종이를 최소로 가위질 해야하는 횟수를 return 하도록 solution 함수를 완성해보세요.
❗제한사항❗
- 0 < M, N < 100
- 종이를 겹쳐서 자를 수 없습니다.
입출력 예
입출력 예 설명
입출력 예 #1
- 본문과 동일합니다.
입출력 예 #2
- 가로 2 세로 5인 종이는 가로로 1번 세로로 8번 총 가위질 9번이 필요합니다.
입출력 예 #3
- 이미 1 * 1 크기이므로 0을 return 합니다.
✔풀이
def solution(M, N):
return (M-1) + (N-1) * M📝설명
문제의 제한조건을 보면 겹쳐서 자를 수 없다고 되어 있다.
정직하게 종이를 자르는 것을 요구하는건데..^^
잘 생각해보면 우리는 종이 한 장을 한 번의 가위질로 2개로, 두 번의 가위질로 3개로, 세 번의 가위질로 4개로 나눌 수 있다.
즉 길이-1의 가위질을 한다면 변의 길이가 1이 되도록 자를 수 있다.
가로를 가위질해서 조건을 충족시켰다면, 세로도 해야 하는데! 세로도 마찬가지로 길이-1의 가위질을 하면 된다.
주의해야 할 점은 겹쳐서 자를 수 없기 때문에, M만큼을 곱해줘야 한다.
예시에 있는 M=2, N=5가 인 경우를 예시로 들어본다면 이해가 더 쉽다.
가로가 2, 세로가 5라고 하면, 우선 가로를 먼저 자른다고 가정하고! 자른다면 한 번의 가위질 (M-1 = 2-1 = 1)로 가로의 길이는 1이 되도록 했다. 이 때 종이는 M과 같이, 2장이 된다.
그 다음 세로가 5인데, 세로를 가위질 4번(N-1 = 5-1 = 4) 한다면, 길이가 1인 조건을 충족한다. 여기에 우리는 앞서 가로를 자르면서 M장이 있기 때문에 M의 값인 2를 곱하면 4 x 2가 되면서 8번을 자른다.
가로 1번, 세로 8번을 더해서 총 9가 return된다.
👑모범 답안
🔎 나의 코드를 좀 더 간결하게 했다.
👀느낀 점
: 오랜만에 많은 사람들과 답안이 유사했다.
며칠전부터 간단하게 해결할 수 있는 문제를 어렵게 접근하고 풀어내서, 약간의 허탈함을 느끼기도 했다.
어쨌든 뿌듯한 건 똑같지만! 그래도 간결하게 접근을 할 수 있다는 걸 나 스스로 증명한 느낌이라 의미있는 문제 풀이였다.
💻 문제 출처