[python] 못생긴 수

이것이 취업을 위한 코딩 테스트다 35번 못생긴 수

문제

풀이

나는 false, true 에 꽂혀서, 어차피 false 에다 true 를 곱하면 false 인데, 대강 그렇게 풀면 되지 않을까라고 생각했다.
그래서 일단 1 빼고 다 false 로 만든 후,
하나씩 true로 바꿔서 answer 에 넣는 방식으로 풀었다.

2로 나누어떨어지고 dp[i//2]가 참일 때,
아니면 3으로 나누어떨어지고 dp[i//3]이 참일 때,
아니면 5로 나누어떨어지고 dp[i//5]가 참일 때.

그러면 어떤 식으로 동작하냐면
i = 2
i % 2 == 0, i // 2 = 1 (True)

i = 3
i % 3 == 0, i // 3 = 1 (True)

i = 4
i % 2 == 0, i // 2 = 2 -> dp[2] = True

이런 식으로 계속해서 가장 최근 숫자를 의존해서 풀어나간다.

n = int(input())
dp = [False] * (1001)  # 충분히 큰 범위로 dp 리스트 생성
dp[1] = True  # 1은 기본적으로 못생긴 수
answer = [1]  # 못생긴 수 리스트, 1은 기본값으로 포함

for i in range(2, 1001):
    if len(answer) == n:  # n번째 못생긴 수를 찾으면 종료
        break

    # 2, 3, 5로 나누어떨어지는 경우만 True로 설정
    if i % 2 == 0 and dp[i // 2]:
        dp[i] = True
    elif i % 3 == 0 and dp[i // 3]:
        dp[i] = True
    elif i % 5 == 0 and dp[i // 5]:
        dp[i] = True

    if dp[i]:  # 못생긴 수일 경우 리스트에 추가
        answer.append(i)

print(answer[-1])  # n번째 못생긴 수 출력