꾸준함

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

문제 링크입니다: https://www.acmicpc.net/problem/2096처음에 작성한 코드는 정답은 맞지만 메모리 초과가 발생하는 코드였습니다.사실 메모리 초과가 발생하지 않는 것이 더 이상한 코드였던 것 같습니다. /* N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다. 먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수..

문제 링크입니다: https://www.acmicpc.net/problem/1890번역이 살짝 아쉬운 문제였습니다.처음에는 해당 칸에 있는 숫자만큼 움직일 수 있는 경우라고 이해해서 답보다 훨씬 많은 경로를 구했습니다.문제에 해당 칸에 있는 숫자만큼 "한 방향"으로 움직일 수가 있다고 했더라면 고생하지 않았을 것 같습니다.답이 2^63 - 1까지 나올 수 있으므로 자료형을 long long으로 선언하는 것이 핵심이였습니다. /* N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 ..

문제 링크입니다: https://www.acmicpc.net/problem/11051이산수학 과목에서 이미 조합을 구하는 점화식을 배웠으므로 쉽게 풀 수 있었던 문제였습니다. /* 자연수 N과 정수 K가 주어졌을 때 이항 계수 (N, K)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오. */ #include #include //memset using namespace std; const int MAX = 1001; const int MOD = 10007; int N, K; //주어진 수 int cache[MAX][MAX]; int binomialCoef(void) //이항계수 { for (int i = 1; i N >> K; if (N = MAX || KN) exit(-1)..

문제 링크입니다: https://www.acmicpc.net/problem/6359다이나믹 프로그래밍 주제에 있던 문제였지만 메모이제이션을 통해 풀지는 않았습니다.동적계획법으로 푸는 것보다 제가 푼 방법이 좀 더 쉬운 방법인 것 같습니다. /*서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다.각 방에는 벌점을 많이 받은 학생들이 구금되어있다.그러던 어느날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다.게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다.그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고, 잠겨있다면 연다. 같..

문제 링크입니다: https://www.acmicpc.net/problem/1937'프로그래밍 대회에서 배우는 알고리즘 문제해결전략' 책에서 익힌 메모이제이션을 통해 문제를 해결했습니다.문제의 조건을 코드로 잘 옮기는 것이 관건이였습니다. /* n*n의 크기의 대나무 숲이 있다.욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다.그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_ - ) 이 판다의 사..

문제 링크입니다: https://www.acmicpc.net/problem/1309사자를 배치하지 않을 경우는 전 줄의 배치에 영향을 받지 않는다는 것이 핵심이였습니다. #include using namespace std; const int MAX = 100000; const int MOD = 9901; int N; int cache[3][MAX + 1]; //0: 없다, 1: 왼쪽에 있다, 2: 오른쪽에 있다 int Lion(void) { //첫 번째 줄에 사자가 없을 수도, 왼쪽에 있을 수도, 오른쪽에 있을 수도 있다 cache[0][1] = cache[1][1] = cache[2][1] = 1; for (int i = 2; i > N; if (NMAX) exit(-1); cout