[프로그래머스/c++] N으로 표현
문제 숫자 N을 사칙연산을 통해 number로 표현할 때 사용되는 N의 최소 사용횟수를 구한다. 접근 규칙을 찾아서 dp 배열을 만들어 적용시키고자 하였으나 무엇을 기준으로 규칙을 찾아야 할 지 감이 잡히지 않아 문제에서 구하고자 하는 것을 다시 살펴보았다. N의 최소 사용횟수를 구한다는 점에서, N을 1개, 2개, 3개 ... 사용해서 만들 수 있는 수들을 직접 적어보았다. 다음 예시를 통해 살펴보자. N number return 2 11 3 dp[cnt]: N을 cnt 개수 만큼 사용하여 만들 수 있는 수 dp[1] - 2 dp[2] - 22 dp[1]과 dp[1]로 사칙연산 - 2+2=4 - 2-2=0 - 2*2=4 - 2/2=1 dp[3] - 222 dp[1]과 dp[2]로 사칙연산 - 2와 22..
알고리즘
2023. 1. 24. 23:22