Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- 자료구조
- Nest.js
- mongoose
- flask
- cookie
- react
- OCR
- MySQL
- nestjs
- jest
- Bull
- Sequelize
- game
- dfs
- Queue
- GIT
- 정렬
- 게임
- 공룡게임
- TypeScript
- Python
- class
- Express
- AWS
- JavaScript
- MongoDB
- typeORM
- Dinosaur
- nodejs
Archives
- Today
- Total
포시코딩
[프로그래머스][Lv.0][재귀] 종이 자르기 본문
728x90
문제
https://school.programmers.co.kr/learn/courses/30/lessons/120922
내 풀이 A
def solution(M, N):
return M*N-1
예시들과 몇가지 따로 만든 예시들로부터 귀납 추론을 통해 N*M-1이면 답을 얻을 수 있는 결과가 나왔지만
이건 아닌 것 같아 다른 방법을 찾아보았다.
내 풀이 B
def solution(M, N):
M, N = min(M, N), max(M, N)
if M == 1:
return N-1
return 1+solution(M-1, N)+solution(M-(M-1), N)
다른 풀이에서 힌트를 얻었는데
종이에 가위질 한 번 할 때마다
1 + 잘린 종이 A + 잘린 종이 B
가 되는 상황을 생각해 재귀 함수로 만들었다.
M을 세로로 생각하고 N을 가로로 생각했는데
세로가 1일 경우 남은 가로 길이에 대해 -1 하면 모두 1x1로 만들었을 때 나오는 종이의 개수와 같아지므로
M == 1일 경우 return N-1이 됐고
M이 1이 아닐 경우 가로로 길게 한번 자른다면
종이 조각 A는 세로가 세로 - 1이 되고
나머지 종이 조각 B의 세로는 위에서 자르고 남은 세로 - 1 만큼 자른 값이 된다.
가로 길이는 그대로
이걸 코드로 나타낸게 위의 코드다.
728x90
'자료구조알고리즘 > 문제풀이' 카테고리의 다른 글
[프로그래머스][Lv.0] 유한소수 판별하기* (0) | 2023.01.10 |
---|---|
[프로그래머스][Lv.0][재귀] 문자열 밀기 (0) | 2023.01.10 |
[프로그래머스][Lv.0] 숨어있는 숫자의 덧셈 (2) (0) | 2023.01.07 |
[프로그래머스][Lv.0] 가까운 수 (0) | 2023.01.07 |
[프로그래머스][Lv.0] A로 B 만들기 (0) | 2023.01.07 |