[algorithm] 백준 13300번 방 배정

 

이 문제는 내 기준에선 꽤나 어려웠다

문제 구조 자체는 쉬워보이나

내부적인 로직을 짤때나 계산 과정이 마냥 쉽지만은 않아 어려움을 겪었다

 

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n,k;
    int a,b;
    int man = 0;
    int woman = 0;
    int room = 0;

    vector<int> vec1;
    vector<int> vec2;
    vector<int> vec3;
    vector<int> vec4;
    vector<int> vec5;
    vector<int> vec6;
    
    cin >> n >> k;
    for (int tmp=0; tmp<n; tmp++)
        {
            cin >> a >> b;
            if(b == 1) vec1.push_back(a);
            if(b == 2) vec2.push_back(a);
            if(b == 3) vec3.push_back(a);
            if(b == 4) vec4.push_back(a);
            if(b == 5) vec5.push_back(a);
            if(b == 6) vec6.push_back(a);           
        }
    
    for (int tmp : vec1)
        {
            if (tmp == 1) man++;
            if (tmp == 0) woman++;
        }
    room += ((man/k) + (man%k));
    room += ((woman/k) + (woman%k));

    man = 0;
    woman= 0;

    for (int tmp : vec2)
        {
            if (tmp == 1) man++;
            if (tmp == 0) woman++;
        }
    room += ((man/k) + (man%k));
    room += ((woman/k) + (woman%k));

    man = 0;
    woman= 0;

    for (int tmp : vec3)
        {
            if (tmp == 1) man++;
            if (tmp == 0) woman++;
        }
    room += ((man/k) + (man%k));
    room += ((woman/k) + (woman%k));

    man = 0;
    woman= 0;

    for (int tmp : vec4)
        {
            if (tmp == 1) man++;
            if (tmp == 0) woman++;
        }
    room += ((man/k) + (man%k));
    room += ((woman/k) + (woman%k));

    man = 0;
    woman= 0;

    for (int tmp : vec5)
        {
            if (tmp == 1) man++;
            if (tmp == 0) woman++;
        }
    room += ((man/k) + (man%k));
    room += ((woman/k) + (woman%k));

    man = 0;
    woman= 0;

    for (int tmp : vec6)
        {
            if (tmp == 1) man++;
            if (tmp == 0) woman++;
        }
    room += ((man/k) + (man%k));
    room += ((woman/k) + (woman%k));
    
    cout << room;
    return 0;
}

 

처음에는 학년 별로 배열을 나눠서

각 배열마다 방 개수를 구해 더해주는 방식으로 풀었다

 

로직을 짜다가 머리가 안돌아가서

테스트케이스만 보고 짠 직관적인 풀이였다(뇌 빼고푼)

 

결론적으론 room을 구하는 계산식도 예외가 존재해서

(k값이 원소값보다 작은 경우 틀린 값 나옴 ex) k=3, 원소값=2)

2점만 획득했다

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n,k;
    int a,b; // a : 성별, b : 학년

    int room = 0;

    int arr[7][2]; // 학년이 6까지 표시돼야하므로 세로줄 7까지 배열잡기
    cin >> n >> k;
    for (int tmp=0; tmp<n; tmp++)
        {
            cin >> a >> b;
            arr[b][a]++;
        }

    for (int tmp=1; tmp<7; tmp++)
        {
          for (int tmp1=0; tmp1<2; tmp1++)
            {
                room += ((arr[tmp][tmp1]/k) + (arr[tmp][tmp1]%k));
            }
        }
    cout << room;
    return 0;
}

 

2차원 풀이로 해결해야 한다는 힌트를 얻고

풀어봤는데 2점도 아니고 그냥 틀렸다는 결과를 받았다

 

우선 아직도 계산식이 잘못된 줄 모르고 있었고

배열을 선언했지만 초기화를 시켜주지 않은 기본적인 실수를 해서 틀린 것이였다

 

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n,k;
    int a,b; // a : 성별, b : 학년

    int room = 0;

    int arr[7][2] = {}; // 학년이 6까지 표시돼야하므로 세로줄 7까지 배열잡기
    cin >> n >> k;
    for (int tmp=0; tmp<n; tmp++)
        {
            cin >> a >> b;
            arr[b][a]++;
        }

    for (int tmp=1; tmp<7; tmp++)
        {
          for (int tmp1=0; tmp1<2; tmp1++)
            {
                if(k>arr[tmp][tmp1] && arr[tmp][tmp1] != 0) room++;
                else room += ((arr[tmp][tmp1]/k) + (arr[tmp][tmp1]%k));
            }
        }

    cout << room;
    return 0;
}

 

이번엔 위에서 언급했던 예외 케이스가 생각나서 따로 처리해줬는데

또 2점을 받게됐다

결국 계산식이 틀린 것이라고 확신하게됐다

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n,k;
    int a,b; // a : 성별, b : 학년

    int room = 0;

    int arr[7][2] = {}; // 학년이 6까지 표시돼야하므로 세로줄 7까지 배열잡기
    cin >> n >> k;
    for (int tmp=0; tmp<n; tmp++)
        {
            cin >> a >> b;
            arr[b][a]++;
        }

    for (int tmp=1; tmp<7; tmp++)
        {
          for (int tmp1=0; tmp1<2; tmp1++)
            {
                if (arr[tmp][tmp1] == 0) continue;
                else if (k>=arr[tmp][tmp1]) room++;
                else
                {
                  while(arr[tmp][tmp1] != 0)
                    {
                        if (k>=arr[tmp][tmp1])
                        {
                            room++;
                            break;
                        }
                        else
                        {
                            arr[tmp][tmp1] -= k;
                            room++;
                        }
                    }
                }
            }
        }

    cout << room;
    return 0;
}

 

최종 정답 코드다

원소값이 0일때 방 수를 카운팅하는 것을 방지했고

원소값이 k보다 클 때

원소값을 k보다 작아질 때까지 k값에 빼주면서 room을 카운트하는 방식이다

 

간단해 보이지만 내부적으로 생각할게 많아 꽤나 복잡하게 느껴졌던 문제였다