[level 2] 카펫
문제
Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.
Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.
Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한사항
- 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
- 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
- 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.
문제 풀이 접근법1
1) 이중반복문을 돌면서 곱했을 때 num이 되는 수 중, weight이 height보다 큰 수의 쌍을 찾아 pari에 추가한다.
2) pair에 있는 숫자쌍 중, 뺐을 때 가장 작은 수의 쌍을 answer에 append한다.
def solution(brown, yellow):
answer = []
num = brown + yellow
min = 1995000
pair = []
for i in range(1, num+1):
for j in range(1, num+1):
if i*j == num and i >= j:
pair.append([i, j])
for i in pair:
if i[0] - i[1] < min:
min = i[0] - i[1]
answer.append(i[0])
answer.append(i[1])
return answer테스트 케이스 3, 5, 6, 7,8, 9, 10에서 시간 초과
테스트 케이스 4에서 실패했다.
하 사실 yellow 최대값이 5,000, 000일때부터 예상은 해서
놀랍지도 않도다
문제 풀이 접근법2
1) 이중반복문을 돌면서 곱했을 때 num이 되는 수 중, weight이 height보다 큰 수의 쌍을 찾아 pari에 추가한다.
2) pair에 있는 숫자쌍 중, 뺐을 때 가장 작은 수의 쌍을 min_pair에 넣는다.
3) 마지막에 min_pair에 저장된 숫자 리스트를 answer에 넣고 반환한다.
def solution(brown, yellow):
answer = []
num = brown + yellow
min = 1995000
pair = []
for i in range(1, (num+1)//2):
for j in range(1, (num+1)//2):
if i*j == num:
pair.append([i, j])
for i in pair:
if abs(i[0] - i[1]) < min:
min = abs(i[0] - i[1])
min_pair = i
answer.append(min_pair[1])
answer.append(min_pair[0])
return answer테스트 케이스 3, 6, 7,8, 9, 10에서 시간 초과
테스트 케이스 4에서 실패했다.
찾아보니까 수가 가장 작다고 해서 조건을 만족하는게 아니었다...그래서 다시 생각해야 했음
그리고 숫자 쌍을 찾는 것도 이중 반복문으로 하면 안될 것 같아서 다시 생각해야 할 필요가 생겨버림
문제 풀이 접근법3
1) num의 약수 쌍을 구하기 위해 num //2 + 만큼 반복문을 돌면서 나누어 떨어지는 i를 찾는다. num을 i로 나눈 값을 mul에 넣고, mul과 i의 쌍을 pair에 저장한다.
2) yellow의 면적은 height와 weight에서 각각 -2를 뺀 값을 곱한 값과 같고, brown의 면적은 전체 면적에서 yellow의 면적을 뺀 값과 같으므로 해당 공식을 사용하여 b와 y를 찾는다.
3) 구한 y와 b의 값이 실제 yellow와 brown의 값과 같은지 확인한다.
4) 맞다면 해당 i를 answer에 넣고 break로 빠져나온다.
def solution(brown, yellow):
answer = []
num = brown + yellow
pair = []
for i in range(1, (num//2)+1):
if num % i == 0:
mul = int(num / i)
pair.append([mul, i])
for i in pair:
y = (i[1] - 2) * (i[0] -2 )
b = num - y
if y == yellow and b == brown:
answer = i
break
return answer
break를 하기 싫으면 처음에 pari에 쌍을 저장할 때 mul>=i를 추가하면 된다. 그러면 사실 중복도 안생기고 좋긴함..
def solution(brown, yellow):
answer = []
num = brown + yellow
pair = []
for i in range(1, (num//2)+1):
if num % i == 0:
mul = int(num / i)
if mul >= i:
pair.append([mul, i])
for i in pair:
y = (i[1] - 2) * (i[0] -2 )
b = num - y
if y == yellow and b == brown:
answer = i
#break
return answer
다른 분들 문제풀이
def solution(brown, red):
for i in range(1, int(red**(1/2))+1):
if red % i == 0:
if 2*(i + red//i) == brown-4:
return [red//i+2, i+2]가로 * 세로 = 격자 합, 둘레의 합(가로*2 + 세로*2 - 겹치는부분4) = 갈색 둘레
....수학 공부 열심히 했어야 했나 진짜.....