[python/1463]1로 만들기

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

정수 X를 10이라고 가정하고 위의 3가지 규칙을 적용하면 아래 그림과 같습니다.

이것을 단계별로 나누면 3단계에서 1을 처음 볼 수 있습니다.

X를 N이라고 가정하고 단계를 리스트에 저장하는 방법은 아래와 같습니다.

lst = []
for i in N:
    # 규칙 3
    lst.append(i - 1)
    # 규칙 1
    if i % 3 == 0:
        lst.append(i // 3)
    # 규칙 2
    if i % 2 == 0:
        lst.append(i // 2)

이 리스트에 중복 값이 있을 수 있기 때문에 중복을 제거해 주어야 합니다.

lst = []
for i in N:
    # 규칙 3
    lst.append(i - 1)
    # 규칙 1
    if i % 3 == 0:
        lst.append(i // 3)
    # 규칙 2
    if i % 2 == 0:
        lst.append(i // 2)
# 중복 제거
lst = list(set(lst))

이것을 Make_1이라는 함수로 만들어줍니다. 그다음 단계에 1이 있을 때까지  while 문을 이용하여 반복시킵니다.

# Make_1함수에서 단계값들 저장
result = [N]
# 단계
cnt = 0
# 1이 있을 때 까지 반복
while True:
    result = Make_1(result)
    cnt += 1
    if result.count(1) == 1:
        break

여기서 주의할 점은 N이 1일 경우는  Make_1 함수를 사용할 필요가 없으니 예외처리를 해주어야 합니다.

 

전체 코드

# 백준 1463 / 1로 만들기
def Make_1(N):
    lst = []
    for i in N:
        # 규칙 3
        lst.append(i - 1)
        # 규칙 1
        if i % 3 == 0:
            lst.append(i // 3)
        # 규칙 2
        if i % 2 == 0:
            lst.append(i // 2)
    # 중복 제거 후 리턴
    return list(set(lst))
 
if __name__=='__main__':
    # 입력 받기
    N = int(input())
 
    # 초기값 설정
    result = [N]
    cnt = 0
 
    # 1이 있을 때 까지 반복
    while True:
        # N이 1일 경우는 할 필요 없음
        if N == 1:
            break
        result = Make_1(result)
        cnt += 1
        if result.count(1) == 1:
            break
    # 출력
    print(cnt)