코드 챌린지 7일차 - 동적 계획법

최소 동전의 수를 구할 때는 그리디 알고리즘으로 해결 가능하다!

만약 나누어 떨어지지않을 때 그리디 알고리즘으로 해결이 불가능하다.

동적 계획법 = DP - 이전 계산한 값을 재사용하여 하나의 문제를 한 번만 풀게 하는 알고리즘!
탑 다운 - 큰 문제부터 풀기 시작하여 작은 문제들을 재귀적으로 호출하여 답을 구하는 방식
바텀 업 - 작은 문제들을 먼저 풀기 시작하여 최종적으로 가장 큰 문제들을 해결하는 방식이다.

배열에 저장하여 반복 작업을 줄이는 기법이 핵심이다.

조건!
겹치는 부분(작은) 문제 - 어떠한 문제가 여러 개의 부분(하위) 문제로 쪼갤 수 있을 때 사용한다.
최적 부분 구조 - 문제의 정답을 작은 문제의 정답에서 구할 수 있을 때 사용한다.

피보나치를 재귀로 구하면 구했던 값을 여러번 구하게 된다.

Dp를 통해 구하면 시간 복잡도가 2^N에서 N으로 확 줄게 된다.

 

 

계기판 조작하기

• 시간 제한: 1초

엘리스는 악질 중고차 딜러인 체셔를 싫어해 체셔를 골탕 먹이려고 합니다.

엘리스는 순식간에 자동차 주행거리 계기판을 조작할 수 있는 기술을 가지고 있습니다. 엘리스는 차를 구경하겠다고 체셔에게 부탁한 뒤 구경하는 시간 동안 계기판의 주행거리를 더 크게 조작해 체셔가 당황하게 만들 예정입니다.

원래 자동차의 주행거리가 N킬로미터면 여러분은 체셔에게 들키지 않도록 주행거리를 N보다 크면서, 가장 작은 수로 늘려놓으려고 합니다. 이때, 조작한 값은 서로 다른 K개의 숫자로 이루어져야 합니다. 예를 들어, 100000이란 수는 1과 0으로 이루어져 있으므로, 2개의 숫자로 이루어진 수입니다.

N과 K를 줬을 때 조작할 수 있는 주행거리의 최솟값을 출력하는 프로그램을 작성하세요.

 

지시사항

입력

• 첫 번째 줄에 자연수 N과 K를 입력합니다.
  
  1≤N≤107
  
  
  1≤K≤10
• 주행거리를 조작한 값이 전과 비교해 더 큰 경우만 입력합니다.

출력

• 첫 번째 줄에 조작할 수 있는 주행거리의 최솟값을 출력합니다.

입력 예시

100000 3

출력 예시

100002

N, K = map(int, input().split())
while len(set(str(N)))< K:
    N = N+1

print(N)

이렇게 짜니까 시간 복잡도가 ...

그래서 줄여보기 위해서 이렇게 해봤는데,...

n,k = map(int, input().strip().split())

if k > len(str(n)) :
    k = len(str(n))
n = n+1
while len(set(str(n)))<k:
    a = 10 * (k - len(set(str(n)))-1) 
    if (a == 0) : 
        a = 1
    n = n+a


print(n)

으림도 없네요

GPT나 클로드 둘 다 아무것도 모르고,..