메밀이네

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

백준 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

DP는 DP인데 문제를 이해하는데 좀 오래걸렸습니다. 간단하게는 모든 코인에 대해 메모제이션을 하면 되지만 메모리제한이 엄격해 다른 방법을 찾아야 합니다. 두번 중첩된 for문을 설명해보자면 1. i가 0부터 n까지 반복문을 실행합니다. 바깥쪽 반복문은 i번째 코인이 사용되는 경우의 수를 구하겠다는 것을 의미합니다. 2. 안쪽에 있는 중첩된 반복문은 i번째 coin의 값부터 시작합니다. 첫번째 반복문을 통해선 무조건 1이 더해집니다(코인값 j와 같은 가치의 코인을 사용하는 경우). 이후 코인값 j에서 i번째 코인의 값을 뺐을때의 값을 구할 수 있는 경우의 수를 더해줍니다. 이 반복문을 통해 coins[i]가 j값을 만들기 위해 사용된 모든 경우의 수를 구할 수 있습니다. 123456789101112131..