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
- 수학
- 코딩테스트
- 프로그래머스
- 재귀
- programmers
- 구현
- 그리디
- 가상메모리
- 브루트포스
- 파이썬
- dict
- level2
- level3
- 다익스트라
- BOJ
- 운영체제
- DP
- 스택
- 딕셔너리
- level1
- 힙
- MYSQL
- 다이나믹 프로그래밍
- 가상메모리 관리
- N과M
- BFS
- level0
- dfs
- 백준
- python
Archives
- Today
- Total
동캄의 코딩도장
프로그래머스 level2 [멀쩡한 사각형] 파이썬 본문
https://programmers.co.kr/learn/courses/30/lessons/62048
코딩테스트 연습 - 멀쩡한 사각형
가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을
programmers.co.kr
처음에는 완전탐색으로 시도했으나 시간초과가 발생하였다.
두번째 시도는 (h>=w)인 환경에서 h/w 값을 계산하여, 한 열당 몇개의 사각형이 잘라지는지로 구하였다.
#프로그래머스 멀쩡한 사각형
import math
def solution(w,h):
if w>h:
w,h=h,w
S=w*h
a=h/w
cnt= math.ceil(a)*w
answer=S-cnt
return answer
이 방법이 맞는 풀이라고 생각했는데, 반례가 있는거같았다. (정확한 반례를 찾지는 못했다.)
결국, 다른 분들의 도움을 얻어 최대공약수로 풀었다.
#프로그래머스 멀쩡한 사각형
import math
def solution(w,h):
if w>h:
w,h=h,w
S=w*h
com=math.gcd(h,w)
answer=S-(h+w-com)
return answer
'코테 > 프로그래머스' 카테고리의 다른 글
프로그래머스 level2 [이진 변환 반복하기] 파이썬 (0) | 2021.12.06 |
---|---|
프로그래머스 level2 [점프와 순간 이동] 파이썬 (0) | 2021.12.06 |
프로그래머스 level3 [추석 트래픽] 파이썬 (0) | 2021.12.02 |
프로그래머스 level2 [압축] 파이썬 (0) | 2021.12.02 |
프로그래머스 level2 [다음 큰 숫자] 파이썬 (0) | 2021.12.02 |