[코테 스터디] DP, 못생긴 수

Q35. 못생긴 수

🐣문제

못생긴 수란 오직 2, 3, 5만을 소인수로 가지는 수를 의미합니다. 다시 말해 오직 2, 3, 5를 약수로 가지는 합성수를 의미합니다. 1은 못생긴 수라고 가정합니다. 따라서 못생긴 수들은 [1, 2, ,3, 4, 5, 6, 8, 9, 10, 12, 15, ... ] 순으ㅡ로 이어지게 됩니다. 이때, n번째 못생긴 수를 찾는 프로그램을 작성하세요. 예를 들어 11번째 못생긴 수는 15입니다.

🐥풀이

생각하던 일반적인 DP 문제와는 조금 다른 유형이었다. DP 테이블 간에서 최소 또는 최대의 값을 찾아 업데이트 시켜가는 것이 일반적인 DP라고 생각했는데, 이 문제는 가능한 모든 (못생긴 수의) 경우를 잡아놓고 최솟값을 하나씩 선택해와서 DP 테이블을 업데이트 시켜 나간다.


못생긴 수는 2, 3, 5만을 약수로 가진 합성수이다. 따라서, 1을 제외하고 2, 3, 5만을 활용하여 수를 만들어나가야 한다. 최솟값을 선택하여 DP에 업데이트 한다. 그 최솟값은 2 또는 3 또는 5를 곱해서 값을 업데이트 시켜 나간다.


쓰면서도 어렵다 @! 코드를 함께 보자!!

# 2, 3, 5에서 시작
two, three, five = 2, 3, 5

# 인덱스
cnt2, cnt3, cnt5 = 0, 0, 0

필요한 소인수는 2, 3, 5 이다. 그럼 각각의 업데이트할 값과 인덱스를 변수 선언해준다.

dp[i] = min(two, three, five)

오름차순이므로 3가지 값 중 최솟값을 골라 dp에 업데이트 한다. (dp[0]=1로 초기화되어 있음)

  if dp[i]==two:
    cnt2 += 1         # 인덱스 올려서
    two = dp[cnt2]*2  # 해당 인덱스 값 *2 업데이트

'2'로 시작하는 변수가 최솟값으로 들어왔을 때, 관련 인덱스를 올려주고 해당 위치의 dp 값과 2를 곱해서 값 변수를 업데이트 한다. (업데이트 값은 다시 min(two, three, five)에서 최솟값 판단 받음)

  if dp[i]==three:
    cnt3 += 1           # 인덱스 올려서
    three = dp[cnt3]*3  # 해당 인덱스 값 *3 업데이트

똑같다. '3'으로 시작하는 변수가 최솟값으로 들어왔을 때, 해당 인덱스 자리의 dp 값과 3을 곱해 값 변수를 업데이트 한다.

  if dp[i]==five:
    cnt5 += 1           # 인덱스 올려서
    five = dp[cnt5]*5   # 해당 인덱스 값 *5 업데이트

마찬가지로 똑같다. '5'로 시작하는 변수가 최솟값으로 들어왔을 때, 해당 인덱스 자리의 dp 값과 5를 곱해 값 변수를 업데이트 한다.


모든 반복문의 과정이 끝났을 때, N번째 못생긴 수는 dp[n-1]에 저장되어 있으므로, 값을 출력하면 되겠다.

🐓코드

# 입력값
n = int(input())

# 2, 3, 5에서 시작
two, three, five = 2, 3, 5
# 인덱스 하나씩 올리기
cnt2, cnt3, cnt5 = 0, 0, 0

# dp 테이블 초기화
dp = [0]*n
dp[0] = 1

for i in range(1,n):
  dp[i] = min(two, three, five)

  if dp[i]==two:
    cnt2 += 1         # 인덱스 올려서
    two = dp[cnt2]*2  # 해당 인덱스 값 *2 업데이트
  if dp[i]==three:
    cnt3 += 1           # 인덱스 올려서
    three = dp[cnt3]*3  # 해당 인덱스 값 *3 업데이트
  if dp[i]==five:
    cnt5 += 1           # 인덱스 올려서
    five = dp[cnt5]*5   # 해당 인덱스 값 *5 업데이트

print(dp[n-1])

⭐2022.05.10

세상엔 정말.. 다양한 유형과 풀이방법이 존재한다. 너무 신박한 풀이였다 😵