궤도

문제 풀이 입력을 계속 스택에 push로 쌓다가 0을 만나면 pop해주면 되겠다. 입력이 끝나면 스택에 남아있는 모든 수를 더해주자. 소스코드 #include #include using namespace std; int main() { int K, input, sum = 0; stack s; cin >> K; for (int i = 0; i > input; if (input == 0) //0이면 가장 위에 있던 수 pop으로 뺌 s.pop(); else s.push(input); } while (!s.empty()) { //스택에 쌓인 모든 수 더해줌 sum += s.top(); s.pop(); } cout

문제 본문 과거 자료구조 수업시간에 C로 스택을 하나하나 정성스레 구현하던 때가 떠오른다. 그때 C++을 잘 모르던 때인데 다행이라고 생각한다. 만약 알고 있었다면 한줄로 해결할 수 있는걸 하나하나 작성하느라 홧병이 나서 죽었을 테니까... C++의 표준 템플릿 라이브러리(STL)중에는 스택이 있다. 그전에 스택이 뭔지 모를 수 있으니 간략히 설명하면 LIFO(Last In First Out) 형식의 자료구조이다. 이 문제는 스택의 기본 사용법을 배우는 그런 문제라고 볼 수 있겠다. www.cplusplus.com/reference/stack/stack/?kw=stack stack - C++ Reference container_typeThe second template parameter (Containe..

문제 풀이 myunji.tistory.com/231?category=1154147 [백준] 1676번 : 팩토리얼 0의 개수 문제 풀이 저 문제 기준으로 10은 1이다. 100은 2고, 1000은 3이다. 즉 해당 팩토리얼을 계산했을 때 10이 몇번이나 곱해졌는지 세어보면 답이 나올 것이다. 10=2x5다. 그니까 팩토리얼을 계산했을 때 myunji.tistory.com 이 문제의 풀이를 거의 그대로 사용할 것이다. nCm = n!/(m!(n-m)!)이다. 그니까 n!과 m!, 그리고 (n-m)!의 2와 5의 수를 각각 구한 뒤, 나눗셈 곱셈을 잘 고려해 계산하면 되겠다. 소스코드 #include #include using namespace std; pair binomial(long long n) { i..

문제 풀이 저 문제 기준으로 10은 1이다. 100은 2고, 1000은 3이다. 즉 해당 팩토리얼을 계산했을 때 10이 몇번이나 곱해졌는지 세어보면 답이 나올 것이다. 10=2x5다. 그니까 팩토리얼을 계산했을 때 곱해진 2의 수와 5의 수를 각각 구해 그 중 작은 것을 택하면 된다. 소스코드 #include #include using namespace std; int fact(int N) { int two_cnt = 0, five_cnt = 0; for (int i = 2; i N; cout

문제 풀이 문제 자체는 아주 쉬운 경우의 수 문제다. 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..