유클리드 호제법을 이용하면 됩니다.#include using namespace std; int getgcd(int a, int b) { int gcd, mod; while (a%b > 0) { mod = a % b; a = b; b = mod; } gcd = b; return gcd; } int main() { int a, b; int gcd, lcm, mod; cin >> a >> b; gcd = getgcd(a, b); lcm = a * b / gcd; cout
#include using namespace std; int main() { int number[8]; int check; for (int i = 0;i > number[i]; } if (number[0] == 1) { for (int i = 1;i < 8;i++) { if (number[i] != number[i - 1] + 1) { check = 3; break; } else { check = 1; } } } else if (number[0] == 8) { for (int i = 1;i < 8;i++) { if (number[i] != number[i - 1] -1) { check = 3; break; } else { check = 2; } } } else { check ..
#include #include using namespace std; int main() { int zerodp[41] = { 0 }; int onedp[41] = { 0 }; vector Nvector; zerodp[0] = 1; onedp[0] = 0; zerodp[1] = 0; onedp[1] = 1; for (int i = 2;i > T; for (int i = 0;i > N; Nvector.push_back(N); } for (int i = 0;i < T;i++) { p..
동적 프로그래밍으로 풀 수 있습니다. 서쪽에 1개 사이트가 있는 경우, 경우의 수는 동쪽의 사이트 개수와 같습니다. 먼저 이 수치로 초기화합니다. 점화식으로 표현하면 dp[1][n]=n 이 되겠습니다. 서쪽에 2개의 사이트가 있는 경우를 생각해보겠습니다. 동쪽에 2개의 사이트의 경우 경우의 수는 1입니다. 서쪽에 2개, 동쪽에 3개인 경우를 생각해보겠습니다. 서쪽 1번에서 동쪽 1번으로 다리를 놓은 경우, 경우의 수는 동쪽 1개의 사이트에서 서쪽 2개의 사이트로 가는 경우의 수가 됩니다. 서쪽 2번에서 동쪽 2번으로 다리를 놓는 경우, 경우의 수는 동쪽 1개의 사이트에서 서쪽 1개의 사이트로 가는 경우의 수가 됩니다. 점화식으로 표현하면 다음과 같습니다. dp[n][m]=dp[n-1][m-1]+dp[n-..
완전 탐색 또는 동적프로그래밍으로 풀 수 있는 문제입니다. 저는 동적프로그래밍을 이용해 풀었습니다. 첫째날->마지막날로 생각하는 것이 아니라 반대로 마지막날->첫째날로 생각하면 더 쉽습니다. 7일부터 시작하겠습니다. 7일에 잡혀있는 상담은 2일이 걸리기 때문에 수행할 수 없습니다. 그러므로 최대이익은 0입니다.6일에도 4일이 걸리는 일이 있기 때문에 최대 이익은 0이 됩니다. 5일에는 2일이 걸리는 일이 있습니다. 5일, 6일에 일을 하고 15를 수익으로 얻는 것이 최대 이익입니다. 4일째는 4일에 1일짜리 일을 하고, 5일까지의 최대 이익을 더해주는 것이 최대 이익이 됩니다. 3일째는 3일에 1일짜리 일을 하고, 4일까지의 최대 이익을 더해주는 겻이 최대 이익이 됩니다. 4일, 3일에는 1일짜리 일이였..
이 문제는 지난 번 풀었던 http://songsunbi.tistory.com/74?category=837207와 거의 비슷합니다. 점화식은 같으나, 한 가지 차이점이 있습니다. 저번 문제에서 조건으로 마지막 계단을 반드시 밟아야 한다는 조건이 있었으나, 이번 문제에세는 마지막 잔을 꼭 마시지 않아도 됩니다. 이를 표현하기 위해 한 줄 더 작성해야 합니다. dp[n]=max(dp[n-1],dp[n]) 아래는 코드입니다. 이해가 안가신다면 위 링크의 설명을 읽어보시면 되겠습니다. #include using namespace std; int wine[10001] = { 0 }; int dp[10001] = { 0 }; int max(int x, int y) { return x > y ? x : y; } in..
이 문제는 동적 프로그래밍을 이용해 해결할 수 있습니다. 문제를 처음보면, 가장 먼저 for문 2개를 이용해 모든 경우의 수를 계산하는 방식이 생각나실 겁니다. 하지만 이 문제는 그렇게 풀면, 시간초과되어 문제를 맞출 수 없습니다. 아래는 코드입니다. #include using namespace std; int list[100001] = { 0 }; int dp[100001] = { 0 }; int max(int x, int y) { return x > y ? x : y; } int main() { int n; int maxvalue = -1000; cin >> n; for (int i = 0;i > list[i + 1]; } dp[1] = list[1]; for (int i..
맨 뒤에 0이오는 경우, 0과 1을 붙일 수 있습니다. 맨 뒤에 1이오는 경우, 0만 붙일 수 있습니다. dp[N][0]을 0으로 끝나는 N자리의 이친수, dp[N][1]을 1로 끝나는 N자리의 이친수라 합니다. N=4일때를 예로 들어보겠습니다. 4자리일때 나올 수 있는 이친수는 1000, 1001, 1010 3개가 있습니다. 3자리일때는 100, 101 2개의 이친수만이 성립합니다. 즉, dp[3][0]=1, dp[3][1]=1이 됩니다. dp[4][0]은 dp[3][0]과 dp[3][1]을 합한 값입니다. 즉, 2가 됩니다. dp[4][1]은 dp[3][0]과 같습니다. 즉, 1이 됩니다. 4자리로 만들 수 있는 총 개수는 위 2개를 합한 3이 됩니다. 정리해보면 dp[N][0] : 0으로 끝나는 N..
동적 프로그래밍을 이용해 푸는 문제입니다. 1, 2, 3의 경우 1의 제곱으로만 구성할 수 있으므로 초기화 해줍니다. 4, 9, 16과 같은 제곱수는 1개의 항으로 구성할 수 있고, 1이 무조건 최소값이 됩니다. 제곱수의 경우, 동적 배열에 1을 저장합니다. 5의 경우를 생각해보겠습니다. 5는 1의 제곱 5개와 2의 제곱 1개, 1의 제곱 한개로 구성가능합니다. 그런데 2의 제곱 4는 이미 1개의 항으로 구성할 수 있음을 알 수 있습니다. 즉, 5의 최소항은 2가 됩니다. 문제에서 예시로 주어진 7의 경우를 생각해보겠습니다. 5의 경우와 마찬가지로 2의 제곱 4는 1개의 항으로 구성함을 알 수 있습니다. 그러므로 7의 최소항은 1+3=4가 됩니다. 11의 경우를 생각해보겠습니다. 11에서 사용할 수 있는..