꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/6603 반복문을 사용해서도 풀 수 있는 것 같은데 언제나처럼 재귀호출을 이용해서 풀었습니다. #include #include #include using namespace std; const int MAX = 6; int k; int lotto[MAX]; int arr[13]; //idx1은 arr의 인덱스, idx2는 lotto의 인덱스 void printLotto(int idx1, int idx2) { //6개 원소 모두 모였을 경우 출력 if (idx2 == MAX) { for (int i = 0; i < MAX; i++) cout

문제 링크입니다: https://www.acmicpc.net/problem/7579 처음에는 가격을 기준으로 인덱스와 총 메모리양으로 메모이제이션을 시도하다가 메모리 초과로 실패했던 문제였습니다.100문제를 넘게 풀었지만 여전히 메모리 초과 에러는 컴파일해야지만 알 수 있는 초보는 웁니다 ㅠㅠ 그 다음에도 여전히 가격을 기준으로 인덱스와 총 가격으로 메모이제이션을 시도해서 테스트 케이스까지는 맞았지만 시스템 케이스에서 틀려 왜맞틀 문제가 되었습니다. 두 번째 시도까지 틀리고 곰곰히 생각해보니 확보할 메모리양이 정확히 M이 아니라 M 이상이라는 것을 파악했습니다.확보해야할 메모리 양이 M 이상이기 때문에 총 메모리양을 기준으로 인덱스와 가격으로 메모이제이션을 진행한 다음,총 가격을 순차적으로 증가시키면서 ..

문제 링크입니다: https://www.acmicpc.net/problem/2688 http://jaimemin.tistory.com/359와 매우 유사한 문제였습니다.계단수와는 다르게 이 문제에서 구하는 것은 줄어들지 않는 숫자이므로 계단수보다는 훨씬 많은 경우의 수가 존재합니다.따라서, int형 대신 long long형으로 결과를 구해야합니다.계단수 문제와 같이 1~9는 이미 조건이 성립하는 숫자이므로 캐쉬에 미리 저장시켜놓고 자릿수 길이를 줄여가면서 경우의 수를 구하면되는 DP 문제였습니다. #include #include //memset using namespace std; const int MAX = 64 + 1; int T, n; long long cache[10][MAX]; //시작하는 수,..

문제 링크입니다: https://www.acmicpc.net/problem/15724 bottom-up DP 문제였습니다.1,1,3,2일 때 region[3][2]+(초록색 직사각형 + 파란색 직사각형 - 하늘색 직사각형)을 하면 범위 내에 있는 사람들의 수를 모두 구할 수 있습니다.그리고 주의할 점은 endl은 시간이 오래걸리기 때문에 시간초과가 발생합니다. 따라서 "\n"을 사용해서 개행을 해줘야합니다. #include #include //memset using namespace std; const int MAX = 1024 + 1; int N, M; int region[MAX][MAX]; int cache[MAX][MAX]; int main(void) { ios_base::sync_with_stdi..

문제 링크입니다: https://www.acmicpc.net/problem/15723 플로이드 알고리즘을 이용해 푸는 그래프 문제였습니다.플로이드 알고리즘을 생각하는 것은 어렵지 않은 문제였지만 굳이 입력을 'a is b' 이런식으로 받는 문제였기 때문에 고생했던 문제였습니다.사실, scanf를 통해 문자열을 입력받으면 바로 해결되는 문제였지만 c++ 문법을 고집하다가 30분 정도 검색을 했던 것 같습니다.결론은, n과 m을 입력받은 다음에 cin.ignore()를 진행해야 버퍼에 아무것도 남지 않아 getline에서 에러가 발생하지 않습니다. #include #include using namespace std; const int INF = 987654321; const int MAX = 26; int ..

문제 링크입니다: https://www.acmicpc.net/problem/15722 예전에 열혈 C 프로그래밍 연습문제를 풀어본 적이 있다면 쉽게 풀 수 있는 문제였습니다.y와 x를 move만큼 이동하고(단, 1초에 1칸씩) move를 증가시킨 다음 반복하면 되는 문제였습니다.주의할 점은 y와 x 좌표를 이동한 다음 부호를 바꾼 다음 y와 x 좌표를 이동해야한다는 점이였습니다. #include using namespace std; typedef struct { int x, y; }coord; coord snail(int n) { coord point{ 0, 0 }; bool sign = true; //sign true -> 양수, sign false -> 음수 int move = 1; //처음엔 1씩 ..

문제 링크입니다: https://www.acmicpc.net/problem/15721 중앙대 CodeRace 2018 문제였습니다.처음 번은 뻔과 데기를 번갈아가면서 외치고 이후에는 cnt번 뻔을 외친 후 cnt번 데기를 외치는 형식이므로 반복문을 잘 적용하면 풀 수 있는 문제였습니다. #include using namespace std; int A, T, chant; int Tth(void) { int bbun = 0; int degi = 0; int cnt = 2; //1회차에 두번 반복 while (1) { //처음 2번은 번갈아가며 for (int i = 0; i < 4; i++) { if (i % 2 == 0) bbun++; else degi++; if (bbun == T && chant == ..

문제 링크입니다: https://www.acmicpc.net/problem/1256 DP 문제였지만 DP만으로는 풀 수 없고 quickSearch 알고리즘처럼 몇번 skip, 즉 건너뛰어야하는지 파악하면서 푸는 문제였습니다.우선, DP를 이용해 'a'와 'z'를 조합해 만들 수 있는 단어들의 갯수를 구합니다.(간단한 방법으로는 factorial(A+Z)/(factorial(A)*factorial(Z))를 통해 갯수를 구할 수 있지만 DP를 사용하지 않을 경우 시간초과가 발생합니다.)만약, 여기서 구한 단어들의 갯수가 K가 더 크다면 해당 단어가 존재하지 않는다는 증거이므로 noWord=true가 됩니다.그 다음 getWord 함수를 통해 K번째 단어를 구하는데 'a'와 'z' 둘 다 더하지 못하는 경우는..

문제 링크입니다: https://www.acmicpc.net/problem/1182 부분집합의 합을 구할 때 해당 인덱스에 있는 숫자를 더하는 경우가 있고 안 더하는 경우가 있는데 이를 모두 고려해준다면 쉽게 답을 구할 수 있는 문제였습니다.개인적으로 종만북에 나온 코드들에 익숙해져 반복문보다는 재귀호출이 더 쉽게 느껴지네요. #include using namespace std; const int MAX = 20; int N, S; int arr[MAX]; int result = 0; void numOfSubset(int idx, int sum) { sum += arr[idx]; //우선 해당 숫자를 더한다 //기저사례: 범위 초과시 if (idx >= N) return; //조건 성립시 if (sum ..

문제 링크입니다: https://www.acmicpc.net/problem/2309 9명의 난쟁이의 합을 우선 구하고 두명의 난쟁이의 키를 뺐을 때 최초로 합이 100이된 경우를 출력해주면 되는 간단한 브루트포스 문제였습니다. #include #include #include using namespace std; const int MAX = 9; vector dwarfHeight; int sum = 0; void snowWhite(void) { for (int i = 0; i < 9; i++) { for (int j = i + 1; j < 9; j++) { //9명 난쟁이 합 중 두명의 난쟁이 합을 뺐을 때 100이 되면 if (sum - dwarfHeight[i] - dwarfHeight[j] == 10..