|c++| sw 8104 조 만들기(수학?)

0. [c++]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWwXCn2KQjEDFATu&categoryId=AWwXCn2KQjEDFATu&categoryType=CODE

1. 풀이

문제의 키 포인트는 N이 홀수인지 짝수인지에 따라서 출력의 형태가 변한다는 점이다.

이 문제에서 포인트는 가장 작은 수부터 오름차순 내림차순을 반복하면서 K개의 조에 인원을 배치하는 점이다.

이러한 특징으로 인해 N이 짝수인 경우 K개의 모든 조는 항상 동일한 실력(조원으로 포함된 인원의 등수의 합)을 가지게 된다.

예시로 N=2, K=4를 보여주자면

2층 8 7 6 5

1층 1 2 3 4

+ ------------

     9 9 9 9

를 가지게 된다.

층이 계속해서 커진다 하더라도, (2k +1) + (2k + 2)층의 합(k>= 0인 정수)은 항상 0을 유지하게 되는 특징을 가진다.

이러한 특징으로 N이 짝수라면 모든 인원의 등수를 더해준 합을 K개로 나누어 각 조에 실력으로 보면 되는 것이다.

이때, 합은 기본적인 수식을 활용하자. 

1부터 N까지 합은 N(N+1)/2인 점을 활용한다.

또한, N이 홀수였던 경우라면, 짝수의 부분을 우선적으로 구한 이후, 가장 위층의 첫번째 수만 ret에 더해주고 ret을 1씩 증가시키면서 출력을 하는 것으로 정답을 구해낼 수 있었다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

#include<iostream>   typedef unsigned long long ull;   using namespace std;   int main(int argc, char** argv) {     ios_base::sync_with_stdio(0);     cin.tie(0);     int test_case;     int T, N, K;          cin >> T;       for (test_case = 1; test_case <= T; ++test_case)     {         cin >> N >> K;           cout << "#" << test_case << " ";         int ret = 0;         if (N % 2 == 0) {             ret = N * (N*K + 1) / 2;             for (int i = 0; i < K; i++) {                 cout << ret << " ";             }         }         else {             ret = (N - 1)*((N - 1)*K + 1) / 2;             ret += (N - 1)*K + 1;             for (int i = 0; i < K; i++) {                 cout << ret++ << " ";             }         }         cout << endl;              }     return 0;//정상종료시 반드시 0을 리턴해야합니다. } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!