꾸준함

문제 링크입니다: 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으로 변환하고 조건에 맞게 변환하여 문제를 푸는데 성공했습니다.

문제 링크입니다: https://www.acmicpc.net/problem/11722http://jaimemin.tistory.com/317와 비슷한 문제였습니다. /* 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. */ #include #include using namespace std; const int MAX = 1000; int N; //수열의 길이 int cache[MAX + 1], arr[MAX]; //arr[start]에서 시작하는 감소 부분 수열 중 최대 길이 반환 int LDS(int start) //Least Decreasing Sequence { int &result = cache[start + 1]; if (result != -1) return..

문제 링크입니다: https://www.acmicpc.net/problem/11055LIS(Largest Increasing Sequence) 문제와 비슷하지만 증가 부분 수열의 최대 길이가 아닌 최대합인 점에서 달랐습니다. /* 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. */ #include #include #include //memset using namespace std; const int MAX = 1000; int N; int arr[MAX]; int cache[MAX]; int maxSum(void) { int result = 0; for (int i = 0; i < N; i++) { cache[i] = arr[i]; //i번째..

문제 링크입니다: https://www.acmicpc.net/problem/11048동 서 남 북을 고려하지 않고 동, 남, 남동 방향만 고려하면 됬기 때문에 쉽게 풀 수 있던 문제였습니다./* 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은(1, 1)이고, 가장 오른쪽 아랫 방은(N, M)이다. 준규는 현재(1, 1)에 있고, (N, M)으로 이동하려고 한다.준규가(r, c)에 있으면, (r + 1, c), (r, c + 1), (r + 1, c + 1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다.또, 미로 밖으로 나갈 수는 없다. 준규가(N, M)으로 이동할 때, ..