생각
최근 DP와 관련해서 고민이 많았었다.
DP의 개념은 동적 프로그래밍이다.
그냥 간략하게 적자면 한번 계산한 연산을 다시 하지 않도록 테이블에 저장한 후 활용하는 것이다.
하지만 요새 문제를 접할 때 마다, 내가 DP 개념을 활용하는건지, 아니면 그냥 풀었던 문제와 비슷한 방식을 대입해서 푸는건지 헷갈렸었다.
다시 한번 명심해야 할 것은 절대 생각없이 대입해서 풀면 안된다는 점이다.
이 개념들이 왜 탄생했는지 생각하고, 이 문제에 해당 개념이 왜 쓰이는지를 인지해야한다.
위의 백준 문제는 DP의 개념을 다시 한번 집어볼 수 있어서 좋았다.
문제 접근 방식
처음에는 완전탐색으로 생각을 하다가 DP를 떠올렸다면 괜찮은 접근 방식이였을 것 같다.
DP는 이전의 구했던 값을 다시 활용하는 것이고, 이는 정화식을 가지게 된다.
처음에는 일일이 다 구해보았고, 그러면서 특징을 찾아내 점화식을 구하였다.
n의 값. 즉 자릿수와 관계없이, 맨 마지막 수가 중요하다고 생각했다.
위 그림에서 10, 12가 있는 상태에서 n = 3일때를 구해보자면
생각해야 할 것은 맨 마지막 숫자이다. 뒤에 올 숫자가 맨 마지막 숫자와 1이 차이가 나면 된다.
그렇게 해서 n = 1일때 나온 수, 1은 0을 만들어내고, 2~8까지의 수는 각자 자기보다 1이 차이나는 수를 만들어 낸다.
이로 인해 해당 그림이 그려지게 되었고, 점화식을 유추해낼 수 있었다.
정답 코드
