꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/10164이산수학에서 배운 조합을 쓴다면 훨씬 간단하게 풀 수 있는 문제입니다.하지만 동적계획법을 연습하고 싶은 관계로 다음과 같이 풀었습니다.*(x+1)+y*M이 격자 안에 있는 숫자입니다. #include #include //memsetusing namespace std; const int MAX = 15; int N, M, K; //두 정수, o로 표시된 칸의 번호int arr[MAX][MAX];long long cache[MAX][MAX]; //(x+1)+y*M -> 격자 안에 있는 숫자long long path(int y, int x){ //기저 사례 if (y == N - 1 && x == M - 1) //목적지에 도달..

문제 링크입니다: https://www.acmicpc.net/problem/20110은 어떠한 알파벳도 아니라는 것을 인지하는 것이 핵심이자 함정이였습니다.그 외에는 숫자를 하나만 보고 A~I로 인지하는 경우의 수, 두개를 보고 J~Z로 인지하는 경우의 수를 합쳤습니다. #include #include using namespace std; const int MAX = 5000 + 1; const int MOD = 1000000; int len; int arr[MAX]; int cache[MAX]; int password(void) { cache[0] = 1; //0 for (int i = 1; i = 1 && arr[i] = MAX) exit(-1); for (int i = 1; i

문제 링크입니다: https://www.acmicpc.net/problem/9507'프로그래밍 대회에서 배우는 알고리즘 문제해결전략'에서 배운 메모이제이션 기법을 사용하여 쉽게 풀 수 있었습니다.주어진 조건대로 재귀함수를 작성하면 됩니다! /* 꿍은 군대에서 진짜 할짓이 없다.그래서 꿍만의 피보나치를 만들어보려고 한다.기존의 피보나치는 너무 단순해서 꿍은 좀더 복잡한 피보나치를 만들어보고자 한다.그래서 다음과 같은 피보나치를 만들었다.꿍만의 피보나치 함수가 koong(n)이라고 할 때, n 3 : koong(n − 1) + koong(n − 2) + koong(n − 3) + koong(n − 4) 이다. 여러분도 꿍 피보나치를 구해보아라. */ ..

문제 링크입니다: https://www.acmicpc.net/problem/1904N-2개 수열에 00을 붙이는 가지수와 N-1개 수열에 1을 붙이는 가지수를 더한 값이 N개 수열 가지수입니다.결국 피보나치 수열이였습니다. /* 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 지원이는 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 N개 수열로 이루어진 모든 2진 수열을 만..

문제 링크입니다: https://www.acmicpc.net/problem/13460처음에는 기존 보드판을 넘겨야한다는 것이 핵심이였습니다.즉, 보드를 전역변수로 선언하여 계산하면 특정 테스트 케이스에서 오류가 발생합니다.저 같은 경우는 board를 전역변수로 선언했을 때 테스트 케이스는 다 맞았는데 항상 4%에서 틀렸다고 나와서 한참을 고민했습니다.결론을 말하자면,6 7 ####### #..BR## #.##### #.#O### #....## #######다음과 같은 테스트 케이스의 답은 8이지만 전역변수로 선언하여 전달하면 9가 나와 오답이 나옵니다. #include #include #include using namespace std; const int INF = 987654321; const int ..

문제 링크입니다: https://www.acmicpc.net/problem/13458input은 int형이지만 output은 long long형으로 하는 것이 핵심이였습니다. /* 총 N개의 시험장이 있고, 각각의 시험장마다 응시자들이 있다.i번 시험장에 있는 응시자의 수는 Ai명이다. 감독관은 총감독관과 부감독관으로 두 종류가 있다. 총감독관은 한 방에서 감시할 수 있는 응시자의 수가 B명이고, 부감독관은 한 방에서 감시할 수 있는 응시자의 수가 C명이다. 각각의 시험장에 총감독관은 오직 1명만 있어야 하고, 부감독관은 여러 명 있어도 된다. 각 시험장마다 응시생들을 모두 감시해야 한다.이 때, 필요한 감독관 수의 최소값을 구하는 프로그램을 작성하시오. */ #include using namespace..

문제 링크입니다: https://www.acmicpc.net/problem/10942scanf와 printf가 cin과 cout보다 얼마나 빠른지 실감할 수 있는 문제였습니다.실제로 함수 코드는 똑같은데 배열을 입력받을 때 cin으로 받으면 시간초과가 발생했고 scanf로 받으면 시간초과가 발생하지 않았습니다.팰린드롬은 우선 양 끝이 같아야하므로 양 끝이 같은지를 확인하고 처음과 마지막 인덱스를 하나씩 줄여가며 재귀함수를 통해 해결해도 되고 비재귀함수를 통해 해결해도 됩니다. #include #include #include //memsetusing namespace std; const int MAX = 2000; int N, M;int arr[MAX + 1];//int cache[MAX + 1][MAX ..

문제 링크입니다: https://www.acmicpc.net/problem/1915(←, ↖, ↑의 인덱스 값 중 최소) + 1이 (i, j)에서 만들 수 있는 가장 큰 정사각형 변의 길이라는 것을 알아내는 것이 핵심이였던 문제였습니다. #include #include #include using namespace std; const int MAX = 1000; int N, M;string arr[MAX];int cache[MAX][MAX]; int getArea(void){ int side = 0; //변의 최대 길이 for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) { //세 방향 확인할 수 없는 경우 if (i == 0 || j == 0) cache[..

문제 링크입니다: https://www.acmicpc.net/problem/11054최근에 자주 풀었던 LIS의 응용문제였습니다.http://jaimemin.tistory.com/317와 다른점이라면 기존에는 해당 인덱스를 시작으로 하는 최대 부분수열의 길이를 캐시에 저장했는데 이 문제에서는 해당 인덱스를 마지막 요소로 하는 최대 부분수열의 길이를 캐시에 저장해야했다는 점입니다.우선 정방향 LIS를 구하고 캐시에 저장한 뒤 반대방향 LIS를 구하고 캐시에 저장했습니다.그 다음 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN 를 만족해야하므로 모든 인덱스를 순회하며 fCache[i]+rCache[i]의 최대값을 찾았습니다. 여기서 주의..

문제 링크입니다: https://www.acmicpc.net/problem/2225K개의 숫자로 N을 구성하는 방법은 K-1개의 숫자로 N-K를 구성하는 방법들의 합이란 것을 이해한다면 쉽게 코드를 작성할 수 있는 문제였습니다. /*0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1 + 2와 2 + 1은 서로 다른 경우).또한 한 개의 수를 여러 번 쓸 수도 있다*/#include #include using namespace std; const int MAX = 200;const int MOD = 1000000000; int N, K;int cache[MAX + 1][MAX + 1]; //N, K int numO..