Dolphins의 HelloWorld

생각보다 간단한 문제이다. memo[n][m]가 의미하는것이 길이가 m이고 끝자리가 n인 계단수라고 하자. 예를들어 길이가 m이고 끝자리가 5일 때 m-1의 길이를 가진것중 끝자리가 4와 6인 갯수를 더한것이 결과값이 될 것이다. 고로 점화식으로 memo[n][m] = memo[n-1][m-1] + memo[n+1][m-1]을 쓰고 특정 case로 끝자리가 0인 경우 앞자리가 1, 9같은경우 앞자리가 8인 경우밖에 성립이 안되므로 이 때는 따로 처리해주자. #include #include #include #define div 1000000000; using namespace std; long long memo[10][101]; int main() { memo[0][1] = 0; for (int i = 1..

먼저 이친수가 한자리 일때는 첫자리는 1 밖에 될 수 없으므로 memo[1] = 1, 두자리 일 떄는 1 뒤에는 0 이 나와야하므로 memo[2] = 1 이다. 이친수의 개수를 구하기 위한 점화식이 무엇인지에 대해 생각해보자. N번째 수가 0이 나오는 경우는 N-1 이친수의 갯수와 같다. 왜냐하면 N-1자리의 모든 이친수들은 뒤에 0을 가질 수 있기 때문이다. 1이 나오는 경우는 N-2의 길이를 가지는 이친수의 갯수와 같은데 N-1이친수가 0이 나오는 갯수만큼 N번째 이친수에서 1이 나오기 때문이다 고로 memo[N] = memo[N-1] + memo[N-2]이다. #include #include #include using namespace std; long long memo[91]; int main()..

풀이 이 문제는 주어진 붕어빵들에 대해 세트를 어떻게 구성해야 최대의 이득을 낼 수 있는지에 관한것이다. 풀이는 생각보다 직관적이다. n개를 선택했을 때 가장 이득이 큰 값을 memo배열에 넣게되는데 예를들어 3개를 선택했을 때 이득이 가장 큰 경우는 memo[2] + num[1] , memo[1] + num[2], memo[0] + num[3] 중 가장 최댓값일 것이다.(여기서 num은 처음에 주어진 단순한 세트의 가격이다.) 이런식으로 처음부터 memo를 구해가면서 답을 도출해내는 것이다. #include #include #include using namespace std; int main() { int memo[1001]; memset(memo, 0, sizeof(int) * 1001); int n..

풀이 기저조건 : 기본 조건인 n = 1, 2, 3 일때 나오는 가짓수는memo[1] = 1 // 1memo[2] = 2 // 1+1 , 2memo[3] = 4 // 1+1+1, 1+2, 2+1, 3 점화식 : n번째 문자를 나타내는 경우의 수는 n-1일 때의 경우에서 1을 붙이는 경우,n-2의 경우에서 2를 붙이는 경우, n-3의 경우에서 3을 붙이는 경우가 있다. 고로 f(n) = f(n-3) + f(n-2) + f(n-1)이다. #include using namespace std; int memo[11]; int main() { int n; int testcase; cin >> testcase; memo[1] = 1; memo[2] = 2; memo[3] = 4; while (testcase--) ..

11726과 거의 흡사한 문제 11726문제에 2x2 타일 하나가 추가 됐을 뿐이다. 고로 2x2의 공간을 한번에 채우는 경우가 2x1 두개, 2x2 하나 총 2가지로 늘었으며 이것을 점화식에 반영하면 f(n) = 2*f(n-2) + f(n-1)이 된다. #include #include #include #include using namespace std; int memo[1001]; int main() { int n; cin >> n; memo[1] = 1; memo[2] = 3; for (int i = 3; i

풀이 기저조건 : n = 1일 때, f(n) = 1n = 2일 때, f(n) = 2 점화식 : 2 x 1 타일의 경우 무조건 2개를 사용하면서 2x2 정사각형을 만듦1 x 2 타일의 경우 전에 있었던 타일로부터 그냥 하나씩 붙이면 됨 고로 f(n) = f(n-2) + f(n-1) 그리고 답이 10007로 나눈 나머지이므로 반복문에서 계속 mod연산을 수행한다.(미리 mod 연산을 해도 최종 답에 영향을 미치지 않음) #include #include #include #include using namespace std; int memo[1001]; int main() { int n; cin >> n; memo[1] = 1; memo[2] = 2; for (int i = 3; i

풀이 첫번째 풀이는 bottom-up 방식을 사용하였다. 연산을 사용해서 끝나는 마지막 값이 1이므로 초기값은 m[1] = 0으로 주었다. 그 후 반복문을 사용하여 구하고자 하는 수까지 반복하면서 세가지 방법중에 가장 작은값이 나오는것을 배열값으로 주었다. 아래는 그 점화식과 코드이다. f(n) = min(f(n-1) + 1, f(n/3) + 1, f(n/2) + 1)) #include #include #include #define SIZE 1000000 //입력값으로 줄 수 있는 최댓값 using namespace std; int memo[SIZE + 1]; //값을 저장하는 배열 int main() { memset(memo, -1, sizeof(int)*(SIZE + 1)); //배열의 모든 값들을 ..

알고리즘문제를 풀며 원하는 기준에 따라 정렬한 후 하나씩 추출하고자할 때 priority_queue를 쓰면 어렵지않게 문제를 풀 수 있다. 가장 간단한 형태로써 priority_queue pq; 라고 선언했을 때는 우선순위 안에 있는 수 중에서 가장 큰 수를 추출해낼 수 있다. 아래의 코드는 그 예시이다. #include #include using namespace std; int main() { priority_queue pq; pq.push(10); pq.push(39); pq.push(23); pq.push(2); pq.push(44); while (!pq.empty()) { printf("%d ", pq.top()); pq.pop(); } } 실제로 우선순위 큐를 구현하는 가장 일반적인 형태는 p..

힙은 완전이진트리를 바탕으로 한 자료구조로써 부모노드가 자식노드보다 크도록 설정해주면 최대힙 그 반대면 최소힙이라고 한다. 만약 최대힙을 구현했다면 루트노드에는 새로운 수를 삽입하든 삭제하든 가장 큰 수가 위치하게된다. 힙에대한 개념이 부족하다면 힙을 공부해보고 힙 소트를 한번 구현해볼 것을 권한다. 어쨌든 이러한 힙의 성질은 우선순위 큐와 일치하며 c++에서 제공하는 라이브러리를 통해 쉽게 문제를 풀 수 있다. #include #include using namespace std; int main() { int N; int num; priority_queue>int> N; while (N--) { cin >> num; if (!num) { pq.empty() ? printf("0\n"..

이 문제에서 가장 중요한 것은 이 문제가 스택을 이용하는 문제라는 것임을 파악하는 것이다. 스택을 이용하지 않는다면 "( [ ) ]" 이런 문자열이 나왔을 때 괄호가 대응되지 않는다는것을 나타내기가 어렵다. 그러나 스택을 쓴다면 스택의 가장 맨 위에있는 괄호가 가장 최근에 쓰여진 괄호이기 때문에 스택의 맨위에 있는것과 새롭게 들어가는 문자를 비교하면서 괄호가 대응되는지 판단하는것이 용이하다. #include #include #include using namespace std; int main() { string s; while (getline(cin, s)) { stack stk; bool b = true; if (s[0] == '.') break; for (int i = 0; i < s.length()..