꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/11060간단한 메모이제이션을 이용하면 쉽게 풀 수 있는 문제였습니다.최대 arr[i]만큼 움직이는 것이므로 1부터 arr[i]만큼 움직여보는 것이 핵심이였습니다. #include #include #include //memset using namespace std; const int INF = 987654321; const int MAX = 1000; int N; int arr[MAX]; int cache[MAX]; int minJump(int start) { if (start == N - 1) //목적지 도달할 경우 return 0; if (start >= N) //목적지 도달 못할 경우 return INF; int &resul..

문제 링크입니다: https://www.acmicpc.net/problem/2302좌석 수 별로 경우의 수를 구하다 보면 간단히 피보나치 수열인 것을 확인할 수 있다.피보나치 수열인 이유는 1. i번째 좌석에 i번 티켓을 가진 사람이 앉게 된다면 i-1개의 좌석의 경우의 수가 되고2. i번째 좌석에 i-1번 티켓을 가진 사람이 앉게 된다면 i-1번 좌석에는 i번 티켓을 가진 사람이 앉게 되므로 i-2개의 좌석의 경우의 수가 된다. 따라서 VIP 좌석이 있다면 0~첫번째 VIP 좌석 사이에 있는 좌석의 수번째 피보나치 수열, 첫번째 VIP 좌석과 두번째 VIP 좌석 사이에 있는 좌석의 수번째 피보나치 수열, ..., i번째 VIP 좌석과 i+1번째 VIP 좌석 사이에 있는 좌석의 수번째 피보나치 수열을 모..

문제 링크입니다: https://www.acmicpc.net/problem/2098http://jaimemin.tistory.com/365와 비슷한 문제였습니다.다른점은 다시 해당 도시로 돌아오는 경로도 더해줘야하고 (i,j)와 (j,i)가 대칭이 아니라는 점이였습니다. #include #include #include //memset using namespace std; const int MAX = 16; const int INF = 987654321; int N; int W[MAX][MAX]; int cache[MAX][1 W[i][j]; int result = INF; memset(cache, -1, sizeof(cache)); cout

문제 링크입니다: https://www.acmicpc.net/problem/2631http://jaimemin.tistory.com/430와 비슷하게 LIS를 떠올리는 것이 핵심인 문제였습니다.결국 어린이들 중 정렬이 안되있는 어린이들만 정렬하면 되므로 (총 어린이 수 - 최대 증가 순열)을 구하면 되는 문제였습니다. #include #include #include //memset using namespace std; const int MAX = 200; int N; int arr[MAX]; int cache[MAX + 1]; int LIS(int start) //Longest Increasing Sequence { int &result = cache[start + 1]; if (result != -1)..

문제 링크입니다: 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..