N으로 표현
-
[프로그래머스] N으로 표현알고리즘/프로그래머스 2021. 8. 17. 21:18
문제 링크 풀이 많은 DP 문제가 그렇듯 점화식만 제대로 세울 수 있으면 어렵지 않은 문제이지만, 꽤 까다로운 문제에 속하는 것 같습니다. 여기에서 d[i]는 solution 함수의 매개변수로 주어지는 N을 i번 사용해서 얻을 수 있는 숫자의 집합으로 정의해 문제를 풀면 수월합니다. 즉 N이 5라면 다음과 같은 점화식을 만들 수 있습니다. d[1] = {5} d[2] = {55, 5+5, 5-5, 5*5, 5/5} d[3] = {555, (5+5) + 5, (5+5) - 5, (5+5) * 5, ... , 55 / 5} 3번째 항부터는 집합의 크기가 커지기 시작합니다. 우리는 규칙을 찾아야 하고요. 일단 N이 i만큼 붙어 있는 숫자 하나는 만들기 쉽습니다. d[4]에는 5555가 있겠지요. d[2]를 보..