백준 1026번 C++ 보물

정렬하지 않고 풀기

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

S = A[0]*B[0] + ... + A[N-1]*B[N-1]

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안된다.

S의 최솟값을 출력하는 프로그램을 작성하시오.

문제 링크 https://www.acmicpc.net/problem/1026

처음에는 도움만 받고 지금도 도움을 받고서 알고리즘 문제를 풀지만

그래도 처음에 시작할 때보단 실력이 늘었겠지 생각이 들어 이전에 틀렸던 문제들을 풀고 있다.

이 문제는 정답률 60%로 낮은 편이 아니지만 내 정답률은...

솔직히 쪽팔리다면 쪽팔린 거다.

23일 전이면 처음 알고리즘 스터디를 시작한 날이다.

'보물' 문제의 '틀렸습니다'는 내  '틀렸습니다'의 반절을 차지한다 ㅋㅋㅋㅋ

그냥 B배열 재배열해도 정답이라는 말도 있긴 한데 나는 그렇게 풀기 싫었다...

그렇게 풀면 문제 의도와 상당히 어긋나는 거 아닌가?

아무튼 수학 문제도 그렇지만 나는 일단 틀리면 문제를 붙잡고 있기 보다는 냅뒀다가 생각나면 다시 보는 스타일이다.

이걸로 당장에 시험을 보는 게 아니라서 가능한 일일 테지만,

이래서 미리미리 공부를 해놔야 하나 보다.

코드

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    int N;
    cin>>N;
 
    int A[50];
    int B[50];
    int chk[50]={0,};
 
    for(int i=0; i<N; i++) {
        cin>>A[i];
    }
 
    for(int i=0; i<N; i++) {
        cin>>B[i];
    }
 
    chk[N]={0,};
    sort(A, A+N);
 
    int sum=0;
    for(int i=0; i<N; i++) {
        int temp=0;
        int idx=0;
        for(int i=0; i<N; i++) {
            if(temp<B[i] && chk[i] == 0) {
                temp=B[i];
                idx=i;
            }
        }
        chk[idx] = 1;
        sum+=A[i]*temp;
    }
 
    cout<<sum;
 
    return 0;
}

algorithm 헤더는 sort 함수를 쓰기 위한 것이다.

삽입 정렬 코드를 넣어서 해줄 수도 있긴 한데 이미 만들어져 있는 sort 함수 갖다 쓰면 퀵 정렬이니까 더 효율적이다.

chk 배열은 최대값 여부를 확인해주기 위한 것이다. 그걸 스터디에서는 '깃발 꽂는다'고 표현하던데 이제야 이해했다.

for문을 돌면서 그때마다 max 값을 확인해 준다. 여기에서는 temp라는 변수인데,

만약 B의 i번째 원소가 temp보다 크고 chk의 i번째 원소가 0이면 temp는 B의 i번째 원소가 된다.

그리고 최대값이 된 B의 원소의 인덱스를 idx라는 변수에 따로 저장을 해준 다음 sum에 더한다.

for문 밖을 빠져나와서 대입하는 이유는 for문 안에서 대입하게 되면 temp값보다 큰 원소마다 1을 대입할 테니까

그러면 깃발 꽂는 의미가 없어진다.

배열 B는 2 7 8 3 1 이므로

for문을 돌며 chk의 원소는

0 0 1 0 0

0 1 1 0 0

0 1 1 1 0

1 1 1 1 0

1 1 1 1 1

이 된다.

0일 경우에만 최대값에 대입해 주기 때문에 그 전 최대값은 대입하지 않고 다음 원소를 탐색하는 것이다.

따라서 가장 큰 값, 2번째로 큰 값, 3번째로 큰 값... 순으로 탐색할 수 있다.

확실히 동적 할당을 안 하니까 편하다.

특히 백준 문제는 0으로 초기화하면 편할 때가 종종 있어서 그냥 정적으로 선언하는 게 훨씬 낫다.

지금까지 문제 푸는 요령 잘 몰라서 틀린 게 한두 개가 아니니까...

수학 문제에 편법이 있듯 이것도 비슷한가 보다 ㅋㅋㅋㅋ

어떤 문제를 도움을 받고 푸는 것이 나쁘다고 생각하지는 않는다.

그래도 완전하게 스스로 풀고 싶다는 생각을 한다.

틀린 문제에 매달리지 않고 생각을 잠시 미뤄두고, 그것을 반복하면 언젠가 그 간격이 줄어들지 않을까?

단기간에 잘하게 되길 바라는 것도 사치겠지