문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/42842
문제 설명
안쪽이 노란색 타일로, 바깥 한 줄을 갈색 타일로 구성된 카펫이 있다. 이 카펫의 갈색, 노란색 타일의 갯수만 알 때 이 카펫의 가로 세로 길이를 구하는 문제
1차 시도 - 통과(?)
사실 통과라고 하긴 좀 그렇다. 왜냠 몇 번 내보고 소소하게 틀린 것들을 수정해서 냈걸랑,,
def solution(brown, yellow):
tmp = []
mul = []
for i in range(1, yellow//2+1):
if yellow%i==0:
tmp.append(i)
tmp.append(yellow)
for i in range(1,len(tmp)//2+1):
print(tmp[-i])
mul.append([tmp[-i], tmp[i-1]])
if len(tmp)%2:
mul.append([tmp[len(tmp)//2],tmp[len(tmp)//2]])
for i in mul:
if (i[0]+i[1])*2+4 == brown:
return [i[0]+2, i[1]+2]내 생각은 이거다.
먼저 노란 타일(m*n)의 약수를 구하고, 약수의 쌍들로 (m+n)*2+4 가 brown과 같은지 확인.
같다면, m+2, n+2가 가로 세로 길이다! 라는 것임.
왜냐면 그려보고 생각해낸 것임
- 일단 테두리가 갈색 타일이므로 m이 노란 타일의 가로 갯수, n이 세로 갯수일 때,
m*2+n*2+4가 갈색 타일의 개수일 것 - 그렇기 때문에 이 값이 brown과 같다면 각각 2개 씩 더해진 값이 가로 세로 길이일 것이다...
사실 다른 풀이는 생각나지 않는다. 근데 (m+n)*2+4 이게 가장 중요한 포인트인 것 같다는 생각은 확실..!
도전 1
이건 다른 사람 풀이를 보고 생각한 것
- 굳이 약수를 모두 구하고 쌍을 만들 필요 없이 그냥 약수 구해 바로
i와yellow//i쌍으로 if 확인해보면 되는 것이었음. - N의 약수를 구할 땐
루트 N까지만 나눠지는지 확인해보면 됨
def solution(brown, yellow):
for i in range(1, int(yellow**(1/2))+1):
if yellow%i==0:
if (i+yellow//i)*2+4 == brown:
return [yellow//i+2, i+2]yellow//i로 나눠지는 i의 짝은 당연히 yellow//i 잖슴... 왜 이 간단한 걸 생각 못했지?
- 그리고 i가 오름차순으로 for문을 돈다면
yellow//i가 당연히i보다 크니까 조건을 만족할 때[yellow//i+2, i+2]를 반환하면 되는거고,,, - 그리고 약수 구할 때 루트 n까지만 확인하는 건 그냥 외워야하는듯
- 근데 이것이 왜냐.. 그것은 루트 N * 루트 N이 N이니까 최대 약수(그니까 최대 약수는 아니고 오름차순(i)으로 N을 나눠서 약수인지 확인할 때(N%i==0?) 그 값(i)의 최대가 루트 N이라는 것)가 루트 N이므로 루트 N까지만 확인하면 된다는 것... 오 깨우쳐버렸다. -이상 루트N 파티-
- 약수 i의 짝은 당연히 N//i 라는 것 !!!!!
도전 2
- 사각형의 넓이를 갖고 풀어보는 방법도 있음. 카펫의 넓이(brown+yellow)를 알고있으니까, 여기서도 약수 쌍을 가로, 세로 길이로 두고 (가로-2)*(세로-2)가 yellow인지 확인하는 방식. 오 이게 더 쉬운 것 같은데?
def solution(brown, yellow):
mn = brown+yellow
for n in range(1, mn+1):
if mn%n!=0:
continue
m = mn//n
if (m-2)*(n-2)==yellow:
return [m,n]이게 더 간단한 방식인 것 같다. 어찌됐든 둘 다 약수를 이용해야한다는 점은 동일
사각형이 나오면 일단 넓이를 생각해보자...
