백준(S4) 1026번: 보물 (C언어 C11 C99)

코드를 보기전에: 이 문제는 정말 심술궂은 그리디 알고리즘 문제다.

코드만 무책임하게 올려놓으면 이해하지말고 답이나 봐 이렇게 버릇없어 보이기 때문에 하나 하나씩 설명하겠다.

 

입력 :첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

 

이렇게 문제를 보고 알아야 하는것들이 있다.

1. N은 50보다 작거나 같은 자연수이다.

2. A와 B각 원소는 100보다 작거나 같은 음이 아닌 정수다.

이렇게 두가지는 꼭 알아야한다.

 

문제를 보면 B의 수를 재배열 하지말고 A의 수를 재배열해서 최솟값을 출력하라고 한다.

문제를 보자마자 내가 생각한 해답은 b의 값이 클수록 a의 값이 작으면 최솟값이 나오지 않을까 였다.

 

코드:

일단 나는 4개의 배열을 전역변수로 설정했다. 각각의 쓰임은 코드를 설명하면서 말하겠다.

#include <stdio.h>
int a[51];
int b[51];
int result[51];
int result1[51];

그 후, N을 입력받고 N의 갯수만큼 A와 B를 입력받았다.

int num;
    scanf("%d", &num);
    for (int s = 0; s < num; s++)
    {
        scanf("%d", &a[s]);
    }
    for (int s = 0; s < num; s++)
    {
        scanf("%d", &b[s]);
    }

 

b의 값들은 움직이면 안되기 때문에 b의 값이 큰 순서대로 result라는 배열에 b의 위치를 넣었다.

이때 cnt를 끝나고 초기화 시키지 않으면, 다음에 쓸때 0이 아닌 num-1의 값부터 시작한다.

int cnt = 0;
    for (int s = 100; s >= 0; s--)
    {
        for (int c = 0; c < num; c++)
        {
            if (s == b[c])
            {
                result[cnt] = c;
                cnt++;
            }
        }
    }cnt = 0;

a의 값은 움직여도 되기 때문에 result1이라는 배열에 a의 값을 작은 순서대로 넣었다.

for (int s = 0; s <= 100; s++)
    {
        for (int c = 0; c < num; c++)
        {
            if (s == a[c])
            {
                result1[cnt] = s;
                cnt++;
            }
        }
    }

 

중요!!

값들을 더할 sum이란 변수를 0으로 초기화 시키고,

문제의 조건이 b는 움직이지 않고 a만 움직이는 것이기때문에 b[result[c]] = result라는 배열에 b의 값이

큰 순서대로 위치가 들어가 있기 때문에 큰 순서대로 나열돼 있다.

result1[c] = a의 값을 작은 순서대로 나열한 배열이다.

이 두개의 값을 더한 값이 최솟값이다.

int sum = 0;
    for (int c = 0; c < num; c++)
    {
        sum += (b[result[c]] * result1[c]);
    }
    printf("%d\n", sum);