C++
-
백준 15990 - 1, 2, 3 더하기 5백준 algorithm 2020. 4. 23. 16:29
=> DP 문제이다. => 기존 문제아 달리 이차원 배열로 하여 문제를 해결하여야 한다. dp[i][j] : i를 1,2,3의 합으로 나타내는 방법의 수, j : 마지막에 사용한 수 dp[i][1] : 바로 전에 사용할 수 있는 수는 2,3 dp[i][2] : 바로 전에 사용할 수 있는 수는 1,3 dp[i][3] : 바로 전에 사용할 수 있는 수는 1,2 if (n - 1 >= 0) { dp[n][1] = (dp[n - 1][2] + dp[n - 1][3]) % mod; } if (n - 2 >= 0) { dp[n][2] = (dp[n - 2][1] + dp[n - 2][3]) % mod; } if (n - 3 >= 0) { dp[n][3] = (dp[n - 3][1] + dp[n - 3][2]) % ..
-
백준 16194 - 카드 구매하기 2백준 algorithm 2020. 4. 15. 02:17
=> 카드 구매하기 1번 문제를 참조하여 풀 수 있다. https://codingham.tistory.com/124 백준 11052 - 카드 구매하기 => DP 문제입니다. => 카드 i개를 구매할 때의 최대 비용을 생각해야 합니다. => D[i] : 카드 i개 구매하는 최대 비용 =>카드 i개를 구매하는 방법의 가짓수 카드 1개 들어있는 카드팩 구매, 카드 i - 1개 구매.. codingham.tistory.com => 위와 다른 것은 최솟값을 구하는 것이다. ***주의점 => 카드를 구매하는 비용은 0보다 크다 => 배열의 초기값 설정을 잘해주어야 한다. => D에 들어갈 수 있는 값의 최댓값은 1000 * 10000이다. ( 카드의 개수 * 카드팩의 가격 ) for(int i=1; i N; vec..
-
백준 11052 - 카드 구매하기백준 algorithm 2020. 4. 14. 15:42
=> DP 문제입니다. => 카드 i개를 구매할 때의 최대 비용을 생각해야 합니다. => D[i] : 카드 i개 구매하는 최대 비용 =>카드 i개를 구매하는 방법의 가짓수 카드 1개 들어있는 카드팩 구매, 카드 i - 1개 구매 카드 2개 들어있는 카드팩 구매, 카드 i - 2개 구매 .... .... .... 카드 i 개 들어있는 카드팩 구매, 카드 0개 구매 이를 나타내면 P[1] + D[i-1] 위와 같이 표현할 수 있습니다. 이를 코드로 표현하면 for(int i=1; i N; vector P(N+1); vector D(N+1); int tmp; for(int i=1; i> tmp; P[i] = tmp; } for(int i=1; i
-
백준 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..
-
백준 11576 - Base Conversion백준 algorithm 2020. 4. 5. 23:15
=> 해당 문제는 원래의 A진법의 수를 10진법으로 바꾼 후, 정이가 사용하는 B진법으로 바꾸는 문제이다. => A진법을 10진법으로 바꾸기 위해서 아래의 문제를 확인하면 된다. https://codingham.tistory.com/117 백준 2745 - 진법 변환 => 진법 변환 2와 달리 B 진법으로 표시되어 있는 수를 10진법으로 변환하면 되는 문제이다. *** 참고 : https://codingham.tistory.com/116 백준 11005 - 진법 변환 2 => 간단한 진법 변환 문제이다. => 진법 변.. codingham.tistory.com =>10진법을 어떠한 n 진법으로 바꾸기 위해서 아래의 문제를 확인하면 된다. https://codingham.tistory.com/116 백준 ..
-
백준 10809 - 알파벳 찾기백준 algorithm 2020. 3. 26. 21:24
=> 배열을 사용해서 간단히 풀 수 있는 문제이다. => 배열 index를 접근하기 위해 해당 값에 'a'를 빼줘야 하는 것을 알아야한다. ***컴파일에러 본인은 아래의 함수를 이용하여 배열 초기화를 했었는데 해당 함수는 GCC 컴파일러에서만 작동한다. int arr[26]={[0 ... 25]=-1}; visual studio에서는 아래 함수를 통해서 배열 전체를 초기화 할 수 있다. int arr[26]; fill_n(arr, 26, -1); #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); //int arr[26]=..
-
백준 1373 - 2진수 8진수백준 algorithm 2020. 3. 26. 20:21
=> 수의길이가 1000000 이므로 실제수로는 구현할 수 없다. => 11, 001, 100 의 예시를 들어보자 => 3, 1, 4 => 위와 같이 뒤에서부터 3개씩 나누어 수를 8진수로 변환할 수 있다. => 4의 자리, 2의 자리, 1의 자리를 차례대로 곱하고 더하여 출력한다. *** string에 있는 숫자를 실제 숫자로 print하기 위해서 '0' 을 빼주고 계산한다. #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); string S; cin >> S; int len = S.length(); if(len%3 == 1) { cout