궤도

문제 풀이 문제 자체는 아주 쉬운 경우의 수 문제다. X, Y 종류의 의상이 있다고 하자. 각 종류별 의상은 이러하다. X - a, b Y - c X 종류의 의상에 대해 선택할 수 있는 경우는 {입지 않음, a, b}이고, Y 종류의 의상에 대해 선택할 수 있는 경우는 {입지 않음, c}이다. 둘다 입지 않을 수는 없으니 3x2-1=5가 선택할 수 있는 총 경우의 수이다. 입력을 잘 처리해서 정리하는게 거의 다인 문제인거다. 소스코드 #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; struct outfit { //옷 정보 저장 string name; string kind; }; struct kindCnt { //종류별 옷의 개..

문제 풀이 myunji.tistory.com/228 [백준] 11050번 : 이항 계수 1 문제 본문 설마 이항 계수를 모르는 사람이 이 글을 보진 않겠지...고등학교 때 배우는 그거다. nCk를 구하면 되는건데 다들 알다시피 공식은 n!/(k!(n-k)!)이다. 이걸 그대로 코드로 작성하면 된다. myunji.tistory.com 이걸 동적 계획법으로 푸는 문제이다. 아마 학교에서 이항 계수에 대해 배웠을 때 파스칼의 삼각형도 들어봤을 것이다. nCk = n-1Ck-1 + n-1Ck 라는 공식을 기억하고 있다면 어렵지 않다. 소스코드 #include using namespace std; int dp[1001][1001] = { 0, }; int binomial(int N, int K) { if (N /..

문제 본문 설마 이항 계수를 모르는 사람이 이 글을 보진 않겠지...고등학교 때 배우는 그거다. nCk를 구하면 되는건데 다들 알다시피 공식은 n!/(k!(n-k)!)이다. 이걸 그대로 코드로 작성하면 된다. 소스코드 #include using namespace std; int binomial(int N, int K) { int m = 1, c = 1; int temp_N = N; int temp_K = K; if (N / 2 < K) { //5C3 같은 경우 K = N - K; temp_K = K; } for (int i = 0; i < K; i++) { m *= temp_N; c *= temp_K; temp_N--; temp_K--; } return m / c; } int main() { int N,..

문제 본문 입력 A, B, C가 있다고 하자. 이 수들을 M으로 나눴을 때의 나머지가 전부 같으니 이를 r이라고 하자. 그리고 입력된 수를 M으로 나눴을 때의 몫을 각각 x, y, z라고 하자. 별로 중요하진 않은 애들이다. 정리하면 A = M*x + r B = M*y + r C = M*z + r 이 된다. 여기서 A-B와 B-C를 해보겠다. A-B = M(w-x) B-C = M(x-y) 편의상 (w-x)를 k로 (x-y)를 l로 놓으면 A-B = Mk, B-C = Ml이 된다. 그니까 M은 (A-B)와 (B-C)의 공약수라는 것이다. 이걸 일반화하면 N개의 숫자가 있는 집합 X로 만들 수 있는 모든 K(K=A-B, A∈B∈X, A≠B)의 공약수가 M이 된다는 것이다. 쉽게 풀어쓰면 집합 X에서 숫자 2..

문제 풀이 주어진 두 수의 최소공배수를 구하는 문제이다. 설마 이 글을 보는 사람 중에 최소공배수를 모르는 사람이 있을 것이라고 생각하진 않는다. 혹시 두 수 A, B와 그들의 최소공배수 X, 최대공약수 Y가 있을 때 이들의 관계를 기억할지 모르겠다만... A*B = X*Y 이다. 초등학교인가 중학교인가에서 배우는 것이니 왜 이렇게 되는 거냐고 묻지 않았으면 좋겠다. 아무튼 내가 하고 싶은 말은 최소공배수를 구하는 문제는 그냥 최대공약수를 구하는 문제와 같다는 것이다. 그럼 최대공약수를 구하는 알고리즘은 어떻게 짜면 좋을까? A=1 ; i--)의 for문을 돌며 처음으로 A%i == 0 && B%i == 0가 되는 i 찾기 2. for(int i=A ; i>=1 ; i/=2)의 for문을 돌며 처음으로 ..

문제 풀이 말도 안되는 상상이지만 이런 생각을 해보자. 모든 도시의 주유소에 차와 연결할 수 있는 아주 긴 호스가 있다고 말이다. 다만 특정 주유소와 호스를 연결하려면 그 주유소까지 가야할 것이다. 그럼 저 자동차의 이동과정을 살펴보자. 일단 출발하기 전 주유를 해야한다. 다음 주유소까지 2km이니 2km 만큼의 기름을 첫번째 주유소에서 주유한다. => 5x2 = 10 두번째 주유소에 도착했다. 지난 주유소보다 가격이 저렴해 여기서 충전하기로 한다. 보라색 호스를 연결하고 3km 만큼의 기름을 주유한다. => 2x3 = 6 세번째 주유소에 도착했다. 연결된 호스의 주유소보다 가격이 비싸 이전 주유소에서 호스를 통해 기름을 받아오기로 했다. => 2x1 = 2 네번째 주유소에 도착했다. 도착지에 왔으니 기..

문제 풀이 풀이는 간단한데, 코드 작성이 까다로울 수 있는 문제이다. 먼저 예제 입력1에 대해 괄호를 치면 어떻게 될까? 55-(50+40)이 될 것이다. 그렇다면 이번엔 55-50+40+10-45+22 뭐 이런식이 있다고 치자. 여기에 괄호를 치면 55-(50+40+10)-(45+22)가 될 것이다. 눈치챘겠지만, 마이너스를 기준으로 양옆에 괄호를 치면 최솟값이 나온다. 그럼 마이너스 하나하나 찾아서 괄호를 쳐야할까? 그런 귀찮은 짓을 할 이유는 없다. 55-(50+40+10)-(45+22) 이 식은 55-(50+40+10+45+22) 이렇게 바꾸어도 똑같은 식이다. 즉, 마이너스가 처음 등장하는 지점을 기준으로 A - B의 형태를 만들어 A, B의 식을 각각 더한뒤 그 둘을 빼주면 최솟값이 나온다. ..

문제 풀이 운영체제때 배운 디스크 스케쥴링 알고리즘들이 떠오르는 문제이다. 거기까지 가지 않더라도 문제를 읽어보면 대충 직감적으로 아~ 이거 인출시간 제일 덜 걸리는 사람 순으로 정렬하면 되겠네~ 할 것이다. 인출시간이 덜 걸리는 순으로 정렬했다고 치고 각 사람마다 기다리고 인출하는데 걸리는 총 시간은 어떻게 될까? 이 식을 보고 무언가 감이 온다면 그대로 코드로 작성하면 된다. 혹시 아직 감이 안왔을 수도 있으니...기다리는 사람의 배열을 arr이라고 하고 걸리는 총 시간을 sum이라고 하면 sum = arr[0]*N + arr[1]*(N-1) + arr[2]*(N-2) + ... + arr[N-1]*1 이다. 소스코드 #include #include using namespace std; int arr..