다이나믹프로그래밍
-
N으로 표현 C++프로그래머스(Programmers) 2022. 1. 2. 10:45
입출력 예 N number return 5 12 4 2 11 3 입출력 예 설명 예제 #1 문제에 나온 예와 같습니다. 예제 #2 11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다. #include #include #include #include // unorderd_set사용 using namespace std; int get_basic(int N, int cnt) { int res = 0; while (cnt > 0) { cnt -= 1; res += N * pow(10, cnt); } return res; } int solution(int N, int number) { int answer = -1; vector s(8); int idx=1; if(N == number) { ret..
-
백준 1463 - 1로 만들기백준 algorithm 2020. 4. 6. 00:34
=> DP 문제이다. => 내가 구해야 하는 것을 우선적으로 문자로 써본다. 내가 구하고자 하는 것 : N 을 1로 만드는데 필요한 최소 연산 횟수 가능한 경우의 수 : 1. i 가 3으로 나누어 떨어질 때 - arr[ i/3 ] + 1 2. i 가 2로 나누어 떨어질 때 - arr[ i/2 ] + 1 3. i 에서 1을 뺄 때 - arr[ i - 1 ] + 1 => 위의 경우 세 가지가 있는 것을 알 수 있다. => DP에는 Top-down 방식과 Bottom-up 방식이 있다. => 본인은 Bottom-up 방식을 선호한다. (Top-down은 재귀를 쓰는데, 재귀를 쓰다 보면 헷갈린다....) *** 둘 중 어느것이 좋다는 것은 없다. 본인이 원하는 방식으로 사용하면 된다. #include #inc..