[C++] 백준 1026번 풀이 (보물)

정민경·2023년 1월 27일
0

baekjoon

목록 보기
25/57
post-thumbnail

- 문제 (1026번) : 보물

  • 크기가 같은 배열 두개가 주어졌을 때 동일한 인덱스에 있는 값끼리 곱한 값을 더한 S의 최솟값 구하는 문제

    ∑ ( A[ i ] * B[ i ] ) 의 최솟값


- 입력 및 출력

[ 입력 ]

  • 첫째 줄에 배열의 크기 N 입력 ( 1 ≤ N ≤ 50 , 자연수 )
  • 두번째 줄에 배열 A에 있는 N 개의 수 입력
  • 세번째 줄에 배열 B에 있는 N 개의 수 입력
  • 배열에 저장되어있는 각 원소는 100보다 작거나 같은 음이아닌 정수

[ 출력 ]

  • 계산한 S의 최솟값 출력

- 문제 풀이

  • 이 문제는 동일 인덱스에 존재하는 값끼리 곱한값을 더하는 문제다.
    이것의 합이 제일 작으면 되므로, 동일 인덱스에 존재하는 값끼리 곱한값이 최소가 되면 되는 것이다.

  • 동일 인덱스에 존재하는 값의 곱이 최소가 되려면,

    배열 A 중에서 가장 큰 값 x 배열 B 중에서 가장 작은 값

    을 구해 더하면 된다.

  • 위와 같이 해결하려면 배열 하나는 내림차순으로, 나머지 배열 하나는 오름차순으로 정렬해 동일 인덱스에 존재하는 값들을 곱한 후 더하면 해결된다.

    ex) A : 1 5 6 3 2 || B : 6 0 1 1 2

    • 배열 A는 오름차순으로 정렬 : 1 2 3 5 6
    • 배열 B는 내림차순으로 정렬 : 6 2 1 1 0
    • 각각의 수를 곱한 후 더한 값이 최소가 된다.

      S = 6x1 + 2x2 + 3x1 + 5x1 + 6x0 = 18


- 최종 코드

0개의 댓글