[백준 BOJ] 6159번 Costume Party (C++/cpp)

문제 설명

https://www.acmicpc.net/problem/6159
 

 

접근 방법 - 기초적인 정렬 활용 문제

백준의 6159번 문제는 정렬을 기반으로 하여 해결할 수 있는 문제이다.
해당 문제는, 하나의 코스튬를 두 마리의 소가 함께 입을 수 있을 때 코스튬을 함께 입을 수 있는 두 마리의 소의 쌍 개수를 구하여 출력하면 되는 문제이다.
이때, 소의 마릿수 -> 코스튬의 길이 -> 각 소의 길이 순으로 입력이 주어지니, 이 점까지 함께 참고하면 되겠다.
(문제 지문 해석본이 게시판에 따로 없어, 대충 챗gpt한테 해석을 물었다. 오역이 있을 수는 있으나, 필요하다면 아래 사진으로 참고하면 되겠다.)

문제 영어 해설본 (feat. 챗gpt)

 
사실 이 문제는 "두 포인터" 알고리즘을 활용한다면, 코드를 보다 더 단순하게 작성할 수 있었을 것 같다.
하지만 그걸 안 쓰고 해결한 것을 보아하니, 당시 필자가 두 포인터를 모른 채로 정렬 + 브루트포스 알고리즘으로 문제를 해결한 것으로 보인다.
그런 이유로 효율적인 풀이법은 아닐 수 있으니, 아래를 확인하기 이전에 꼭 참고해주길 바란다.
 
자세한 설명은 아래에 기재해놓으니, 혹여나 해당 문제를 해결하는 데에 어려움을 느끼고 있다면 아래의 설명과 코드를 참고해보길 바란다.
필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.
 

코드의 실행 순서

1) 각 소의 길이를 저장할 배열(cow)을 전역 변수로 선언해둔다.
(소 마릿수의 최대가 20,000인 점을 감안하여, 배열의 크기를 설하였다.)
 
2) 소의 마릿수(n)와 코스튬의 길이(size)를 입력받는다.
 
3) n의 크기만큼 반복문을 수행하여, 각 소의 길이를 입력받고 이를 cow에 하나씩 저장하도록 한다.
 
4) sort() 함수를 통하여, cow의 값들을 오름차순 정렬해둔다.
 
5) 코스튬을 입을 수 있는 소의 쌍 개수를 저장할 변수 cnt를 0으로 초기화하여 선언해둔다.
 
6) 2중 반복문을 통하여, 코스튬을 입혀볼 2마리의 소를 각각 지정하도록 한다.
(j는 i보다 항상 크게 하여, 소의 쌍을 카운트하는 데에 있어 중복이 되는 값이 없도록 하였다.)
- 지정된 2마리의 소의 길이를 합한 값을 임의의 변수 sum에 저장한다.
- sum의 값이 size보다 작거나 같다면, 이 2마리의 소는 코스튬을 함께 입을 수 있음을 의미한다. 따라서 이 경우엔, cnt에 1을 더하도록 한다.
다만 size보다 크다면, 이때엔 j가 제어변수인 안쪽 반복문을 더 이상 돌릴 필요가 없기 때문에 break를 수행하여서 i가 다른 소를 가리키게끔 한다.
(cow 배열의 값들은 현재 오름차순 정렬이 되어있는 상태이며, j가 커질수록 소의 길이 합도 함께 커지기 때문에 이때에 break를 사용하여도 연산을 수행하는 데에는 지장이 없다.)
 
7) 위 연산을 모두 완료하였다면, 최종적으로 저장된 cnt의 값을 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <algorithm>
#define endl '\n'
using namespace std;

//백준 6159번 코드
int cow[20001];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);   cout.tie(NULL);

    int n, size;
    cin >> n >> size;
    for (int i = 0; i < n; i++) {
        cin >> cow[i];
    }
    sort(cow, cow + n);

    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int sum = cow[i] + cow[j];
            if (sum > size) { break; }
            cnt++;
        }
    }
    cout << cnt << endl;
}

 

제출 결과

(2023.02.09 백준 6159번 문제 제출 결과)
이번엔 설명을 잘 한건지 모르겠다;; 확실히 풀이가 좀 엉망이었던 것 같다...