[규칙성 찾기] 프로그래머스-카펫

https://school.programmers.co.kr/learn/courses/30/lessons/42842?language=python3

프로그래머스

 

완전 탐색 카테고리라고 하지만.. 사실 전에 1+2+3더하기 문제처럼 규칙성을 찾는 문제라고 생각하였다. 

우선 본 문제에서 중요한 관점은 3가지 포인트라고 생각하였다. 

1. 가로, 세로의 값의 설정에 따라 직사각형 모양이 다를 수 있음

2. Boundary를 감싸고 있는 수의 규칙성을 찾아보기

3. 가로, 세로의 길이를 구하는 규칙성을 찾아보기

 

 

먼저 1번에 나온 내용처럼 모양이 다를 수 있다는 점의 의미는 아래 그림과 같다. 

만약 동일하게 yellow가 예를 들어 12가 주어질 때 이는 아래 그림처럼 6x2인 경우도 존재할 수 있고 4x3인 경우도 존재할 수 있다. 이 때는 각각 brown의 수가 20과 16으로 다른 케이스가 된다. 

즉, 예를 들어 우리가 보고자 하는 케이스가 첫 번째의 6x2인지 4x3인지 구분을 하기 위한 조건이 필요하다.

이를 위해서는 먼저 우리가 바라보는 케이스 중에서 주어진 brown의 수와 맞는 지를 판단하는 부분을 추가해주어야 한다.

이를 위해 먼저 첫 번째로 구현해야 하는 부분은 바로, 주어지는 yellow 수에 맞는 약수들을 찾는 공식이다. 
즉, yellow가 12라고 하면 이는 
1x12, 2x6, 3x4과 같은 수들이 주어지므로 이들의 케이스를 각각 조사하여 brown의 수와 맞는 지를 확인해야 하므로 먼저 후보군을 구하는 코드를 짜준다.

여기서 나는 주어지는 수의 루트 값을 기준으로 low와 high를 나누어 저장하였다. 예를 들어 12의 경우
low = [1,2,3]
high = [4,6,12] 
이렇게 된다. 그리고 high를 역으로 sort해주면
low = [1,2,3]
high = [12,6,4]

이렇게 index 당 약수의 pair가 구해지게 된다.

자 이제 이를 바탕으로 brown의 수를 구하는 규칙을 찾아야 하는데, 여기서는 일일이 케이스를 분석해서 규칙성을 찾아보았다.

먼저 가로가 1씩 증가할 때마다 어떠한 규칙성이 있는 지를 확인해보았다.

아래 수식처럼 1x1 에서 2x1, 3x1로 넘어갈 때 마다 위 그림에 수식으로 적어놓은 규칙이 있음을 확인하였고 

반면 세로로 증가시킨 경우는, 예를 들어 2x1에서 2x2로 넘어가는 경우 아래 그림과 같은 규칙이 형성된다. 

우선 이렇게 brown의 수를 찾아주는 규칙을 발견하고 이것이 주어지는 brown과 일치하는 경우의 가로, 세로 값을 구해주면 된다.

그러면 이제 가로, 세로의 수를 구하는 일만 남았다.
이것도 하나씩 케이스를 구해가며 규칙을 찾은 결과

위 빨간색 수식처럼 공식을 발견할 수 있었다.

이렇게 공식을 적용한 코드를 짜면 아래와 같다.

def solution(brown, yellow):
    root = (yellow**0.5)
    low = []; high = []
    
    ### 약수를 통해 가로, 세로 후보군들 저장
    for i in range(1, yellow+1) : 
        if i > root : 
            break
        if yellow%i == 0 :
            low.append(i)
            high.append(yellow//i)
    
    ### 이 과정을 통해 약수 pair를 맞춤
    high = sorted(high,reverse=True)
    
    for k in range(len(low)) : 
        now_y = low[k]
        now_x = high[k]
    	
        ### 공식을 통해 주어진 가로, 세로에 대한 brown 값 구함
        brown_expect = 2*(3+(now_x-1))+2*(now_y)
        
        ### 만약 구한 brown 값이 실제 주어진 brown과 일치하면 우리가 원하는 케이스
        if brown_expect == brown : 
        	### 규칙성을 통해 가로, 세로 구함
            bound_x = 3+(now_x-1)
            bound_y = 3+(now_y-1)
            ### 최종 반환
            return [bound_x,bound_y]

 

사실 규칙성 문제는 그냥 계속 끄적여가며 규칙을 찾는 연습을 해보고 문제를 많이 풀어보는 수밖에 답이 없는거 같다...

더 연습하자..