메밀이네

3036번 문제입니다. 링이라고 쓰고 톱니바퀴라고 읽는것의 갯수가 n으로 주어지고, 해당 바퀴의 반지름이 다음줄에 입력으로 주어집니다. 출력은 첫째 바퀴가 1바퀴 돌동안 나머지 바퀴가 몇바퀴 도는지 기약분수의 형태로 출력하는건데요,, 이 문제가 최대공약수/최소공배수 카테고리에 들어가있습니다. 그걸 바탕으로 예제 출력값을 면밀히 관찰하시면 정답이 보입니다. 첫째 바퀴와 n번째 바퀴의 최대공약수로 첫째 바퀴를 나눈것이 분자, n번째 바퀴를 나눈것이 분모입니다. 12345678910111213141516171819202122232425#include int gcd(int a, int b) { int c; while (b) { c = a % b; a = b; b = c; } return a;} int main(..

2981번 검문 문제입니다. 문제 이름과 상관없이 n개의 자연수를 나눴을 때 일정한 값이 나오는 i(2개 이상이 될수 있음)을 찾는 문제입니다. 상황을 수식으로 표현하면 i번째 자연수 A[i]를 나머지가 j인 임의의 정수 m으로 나눴을때의 A[i]는 임의의 정수 k[i] * m + j라고 표현할 수 있습니다. 변수 m이 우리가 구하고자 하는 값이므로, j를 없애기 위해 A[i]와 A[i-1]을 계산해봅니다. A[i] - A[i-1] = m * (k[i] - k[i-1]) 으로 정리할 수 있습니다. 이제 m을 구하기 위해서 i번째와 i-1번째 자연수 값의 차이를 구하고, 그 과정에서 등장하는 최대공약수와 그의 약수들을 구하면 됩니다. 컴퓨터공학을 위해 수학을 배워야 하는 이유가 꾸준히 나타나는 것 같습니다..

LCS2 문제로 LCS(Sequence)의 값과 더불어 문자열까지 출력하는 문제입니다. LCS를 찾는 dp배열에서 문자열을 저장해두면 되지 않을까 생각했는데 생각만으로 끝냈습니다. 구현은 LCS를 찾기 위해 진행된 반복문을 역순으로 추적해서 문자를 스택에 넣고(역순으로 출력해야되기 때문에) 빼면서 출력했습니다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include #include #include int max(int a, int b) { return a > b ? a : b;} int main() { char str1[1001]; char str2[1001]; scanf..

파도반 수열 문제입니다. 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 ... 뭔가 규칙이 있을것만 같은 배열입니다. 실제로 규칙을 찾아보면 6번째값인 3부터 규칙을 찾을 수 있습니다. i번째 파도반 수열의 값은 i-1번째 값 에 i-5번째 값을 더하면 나옵니다. 이전문제에 시간을 쏟은걸 생각하면 너무 쉽게 풀린 문제입니다. 1234567891011121314151617181920212223#include int main() { int t; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); int fixed[6] = { 1, 1, 1, 2, 2, 3 }; int* dp = new int[n + 1]; for (int i = 1; i

2일을 헤맸습니다... 동적계획법으로 1부터 k(소설 장 수)까지의 최소 부분합을 구하는 문제입니다. dp[i][j]는 i장부터 j장까지의 최소합을 메모제이션 합니다. 그런데 자꾸 오답이 떠서 다른분들의 코드를 살펴봤더니 페이지의 부분합을 dp에 더해주더라구요. 그런데 저는 최소합에 왜 부분합을 더하지??를 2일동안 이해해보려고 하다가... 자려고 누웠는데 혹시 dp에 저장되는 값이 부분합만 있는것은 아닐까? 라고 생각한 결과 코드를 이해하는데 성공했습니다... 이지의 부분합을 더하기 전 dp[i][j]에는 i부터 j까지의 페이지의 결합을 위한 값만이 저장되므로 모든 페이지를 합치는 경우의 값이 안들어가게 되는것이었습니다. 2일이나 걸렸지만(사실 오늘을 합하면 3일) 알고리즘을 모두 이해할 수 있어서 뿌..

백준 1520번 내리막길 문제입니다. 시작지점부터 접근해보려고했으나 DP로 풀기 힘들다는 결론을 내리고 역순으로 접근했습니다. 도착지의 경우의 수 = 상하좌우 중 올라갈수 있는곳의 경우의 수를 모두 더한 값 입니다. 한번 방문한 지역은 다시 방문하지 않아야 시간 초과가 뜨지 않습니다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include int n, m;int** maps;unsigned int** ways;int xWays[4] = { -1, 0, 1, 0 };int yWays[4] = { 0, -1, 0, 1 }; int findWay(int y, int x) { //시작점일경우 방법..

와인 마시기 문제입니다. 와인을 연속으로 세잔 마실수 없다는 부분만 캐치하면 쉽게 풀 수 있습니다. 고려해야 하는 경우의 수는 현재의 와인을 합쳐서 두번 연속 와인을 마시기, 이전의 와인을 마시지 않고 현재의 와인 마시기, 현재의 와인을 마시지 않기 세가지입니다. 코드 또한 간단합니다. 123456789101112131415161718192021222324252627282930#include int max(int a, int b) { return a > b ? a : b;} int main() { int n; scanf("%d", &n); int *wines = new int[10001](); wines[0] = 0; for (int i = 1; i