꾸준함

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

문제 링크입니다: https://www.acmicpc.net/problem/1965사실상 최대 증가부분 수열의 길이 구하기 문제였습니다.예전에도 LIS 문제를 풀어봤기 때문에 쉽게 구현할 수 있었습니다. /* 정육면체 모양의 상자들이 일렬로 늘어서 있다. 상자들마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가(1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자들을 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다.앞의 예에서 차례대로 크기가 1, 2, 3, 7..

문제 링크입니다: https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 앞서 http://jaimemin.tistory.com/324?category=987849에서 작성한 코드에서 자료형을 int에서 long long으로 변환하고 조건에 맞게 변환하여 문제를 푸는데 성공했습니다.