[C#] 백준 1026번 보물

[ 문제 ]

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

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

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

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

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

 

[ 코드 ]

1. 내 코드

int n = int.Parse(Console.ReadLine());
int[] a = Console.ReadLine().Split().Select(int.Parse).ToArray();
int[] b = Console.ReadLine().Split().Select(int.Parse).ToArray();
int s = 0;

for (int i = 0; i < n; i++)
{
    int aMaxIndex = Array.IndexOf(a, a.Where((val, idx) => a[idx] != -1).Max());
    int bMinIndex = Array.IndexOf(b, b.Where((val, idx) => b[idx] != -1).Min());

    if (a[aMaxIndex] >= 0 && b[bMinIndex] >= 0)
    {
        s += a[aMaxIndex] * b[bMinIndex];

        a[aMaxIndex] = -1;
        b[bMinIndex] = -1;
    }
}

Console.Write(s);

 

2. 다른 사람 코드

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace BaekJoon_s_Note
{

    class Program
    {
        static void Main(string[] args)
        {
            Console.ReadLine();
            int[] A = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int[] B = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

            int result = 0;

            Array.Sort(A);
            Array.Sort(B);
            Array.Reverse(B);

            for (int i = 0; i < A.Length; i++)
            {
                result += A[i] * B[i];
            }
            Console.WriteLine(result);
        }
    }
}

 

B배열은 재배열하지말라는게 문제에 나와있긴하지만 실제로 내 코드처럼 푸는거나 다른 사람처럼 푸는거나 똑같다.

A배열에서는 최대, B배열에서는 최소를 찾아서 곱을 하기때문에 정렬을 하는거나 다름이 없다.

 

나는 이미 방문한(이미 사용한) 배열의 값은 -1로 바꾸고 where으로 -1이 아닌 인덱스를 찾는 코드로 썼다.

 

[ 실행화면 ]

case: 1

case: 2

case: 3

 

 

 

 

 

---

깃허브 링크: https://github.com/MilkyQuartz/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Silver/1026.%E2%80%85%EB%B3%B4%EB%AC%BC

Algorithm/백준/Silver/1026. 보물 at main · MilkyQuartz/Algorithm

 

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

1026번: 보물