문제https://www.acmicpc.net/problem/2193풀이과정쉬운 계단 수, 오르막 수를 풀어보고 나니 쉽게 풀 수 있었다. 먼저, D[1][0] 은 이친수의 조건 1규칙을 위반하기 때문에 0개였으며 D[1][1] 은 그냥 한개이다. 그 이후로 계속 생각해 본 결과 D[i][0]은 길이가 i-1인 수의 마지막 숫자가 0과 1일 경우의 이친수 개수를 더하면 됐다. 하지만 D[i][1] 의 경우는 이친수의 조건 2번을 적용하면 길이가 i-1이고 마지막 숫자가 0인 경우의 이친수의 개수와 같다는 사실을 알 수 있다. 이러한 결과를 식으로 나타내면 아래와 같다. D[i][0] = D[i-1][0] + D[i-1][1] D[i][1] = D[i-1][0] 소스코드#include using names..
문제https://www.acmicpc.net/problem/11057풀이과정쉬운 계단 수 문제와 비슷한 문제이다. D[i][j] = 숫자의 길이가 i이며 마지막 숫자가 j인 수의 오르막 수의 개수라고 정하고 규칙을 찾아봤다. 그 결과로 길이가 i, 마지막 숫자가 j인 숫자의 오르막 수의 개수는 길이가 i-1이고, 마지막 숫자가 j 이하인 숫자들의 오르막 개수를 모두 더하면 됐다. 식으로 나타내보면 아래와 같다. D[i][j] += D[i-1][k] (0#include using namespace std; #define NUM_MAX 10 // 0~9 까지의 수 (10개) #define mod 10007 int N,ans; long long D[1001][NUM_MAX]; // D[i][j] = 수의 길..
문제 출처 : https://www.acmicpc.net/problem/2309 풀이과정 아홉명의 난쟁이 중에 진짜 난쟁이 일곱명을 추려내는 문제이다. 일곱 난쟁이의 키의 합은 100이라는 사실을 이용해 풀이하면 된다. 9명 중 2명을 선택해 난쟁이가 아니라고 생각하고 나머지 7명의 키 합이 100이면 된다.9명 중 2명을 선택하는 경우의 수가 36가지 이므로 완전 탐색으로 풀었다.코드가 더러운 것 같다. 불필요한 과정을 생각해서 코드를 깔끔하게 바꾸는 연습도 해야겠다. 소스코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #include #include using namespace std..
문제 출처 : https://www.acmicpc.net/problem/11502 풀이과정 D[i] 를 붕어빵 i개를 팔아서 얻을 수 있는 최대 수익이라고 할 때,가능한 경우를 생각해보면 붕어빵 1개를 P[1]에 팔 경우에 남은 붕어빵의 개수는 i-1개가 되는데이 경우에 P[1]+D[i-1] 라는 생각을 할 수 있다. 하지만 D[i]는 얻을 수 있는 '최대' 수익이기 때문에 최대값만 저장해야한다. 그러므로 아래와 같은 식을 생각할 수 있다.D[i] = max(D[i],D[i-j]+P[j])이러한 식을 이용하면 쉽게 해결할 수 있다.DP문제는 많이 풀어보면 감이 온다고 했는데 점점 감이 오는거 같아 기분좋다. 소스코드 1234567891011121314151617181920212223242526272829..
문제 출처 : https://www.acmicpc.net/problem/10844 풀이과정 D[i]를 길이가 i인 수의 계단수의 개수라고 생각해보고 풀려고 하다가 시간을 엄청 날려먹었다.결국 검색을 통해 답을 보고 해결했다. D[i][j]를 길이가 i, 마지막 수가 j인 수의 계단수의 개수라고 생각하고 풀면 된다고 한다.그러면 D[i][j] = D[i-1][j-1] + D[i-1][j+1] 이라는 식이 나온다고 말한다.식만봐서는 이해하기 힘들어서 직접 길이가 3이고 마지막 수가 3인 경우를 생각해봤다.D[3][3]은 직접 경우를 따져보니 123, 323, 343, 543 총 4개였다. 이렇게 직접해보니 위의 식이 이해가 됐다. 소스코드 12345678910111213141516171819202122232..
문제 출처 : https://www.acmicpc.net/problem/1932 풀이과정 DP를 활용하면 간단하게 풀 수 있는 문제이다.맨 왼쪽과 맨 오른쪽을 제외한 곳은 오른쪽, 왼쪽 중 큰 것을 더하여 저장하며, 맨 왼쪽, 오른쪽은 정해진 수를 더해서 저장한다. 소스코드123456789101112131415161718192021222324252627282930#include #include using namespace std; int n,ans;int DP[501][501]; int main(){ cin.sync_with_stdio(false); cin >> n; for (int i = 1; i DP[i][j]; if (j == 1) DP[i][j] = DP[i - 1][j] + DP[i][j]; /..
문제 출처 : https://www.acmicpc.net/problem/2606 풀이과정 처음에 문제를 보고 아 BFS나 DFS를 사용하면 되겠다 라고 생각했는데 밑에 알고리즘 분류에 플로이드-워샬 알고리즘이라고 적힌 것을 보고 플로이드-워샬 알고리즘에 대해 찾아보고 사용해보려고 했는데 너무 어려운 것 같다.그리고 검색해보니 사람들도 주로 BFS, DFS를 이용하여 풀어서 DFS를 이용해서 풀었다.DFS, BFS 에 대한 개념은 머리에 있는데 아직은 구현이 매끄럽게 되지 않는 것 같다. 소스코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #include using nam..
문제 출처 : https://www.acmicpc.net/problem/11655 풀이과정 알파벳을 13칸씩 밀려서 출력하는 문제이다. 아스키코드를 참고하면 쉽게 풀 수 있다.시험기간이라서 쉬운 문제를 풀었다. getline(cin,s)로 한 줄을 입력받아 문자열 처리를 하면 된다. 소스코드1234567891011121314151617181920212223242526272829#include #include std::string s; int main(){ std::getline(std::cin, s); int len = s.length(); for (int i = 0; i = 'A' && s[i] 90) s[i] -= 13; else s[i] += 13; } else if (s[i] >= 'a' && s..
문제 출처 : https://www.acmicpc.net/problem/1158 풀이과정 1부터 n까지의 정수를 큐를 활용하여 저장한 후에 m번째 사람의 제거를 위해 반복문을 돌린다.m번째가 아닌 사람들은 front에서 나간 후 다시 back으로 넣어준다.큐를 활용하면 쉬운 문제였다. 소스코드 12345678910111213141516171819202122232425262728293031323334#include #include using namespace std; int main() { int n, m; cin.sync_with_stdio(false); cin >> n >> m; queue q; for (int i = 1; i
문제 출처 : https://www.acmicpc.net/problem/1894 풀이과정 스택을 활용하는 문제이다. 처음에 문제를 읽었을 때 무슨 소리인지 몰라서 당황했다.이 문제의 핵심은 1~n 까지는 무조건 스택에 들어간다는 것과 pop하는 조건을 잘 찾는 점인거 같다.A를 1~n까지 저장하는 스택이라 하고, B를 입력된 수열을 저장하는 배열이라고 가정할 경우 A.pop()을 하는 조건은 다음과 같다.1. A.top()과 B[i] 가 같을 경우 A.pop()을 통하여 입력된 수열을 만든다.2. 이 과정은 스택이 비어있다면 진행하지 않는다.소스코드를 보고 이해하는 게 더 빠를 거 같다. 소스코드 123456789101112131415161718192021222324252627282930313233343..