백준 알고리즘 1026 보물 | Baekjoon Algorithm 1026 Treasure

이번 학기부터 알고리즘 스터디 Imergoroup을 시작했습니다!

매주 3개 문제를 풀며 화,목,토 마다 업로드 할 예정입니다.

사실 지금 화요일에 푼 문제 1415를 아직도 해결을 못하고 있는상태입니다ㅠㅜ

 

일단 이번 목요일 과제였던 1026번 문제 경험을 공유합니다.

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

1026번: 보물

 

아이패드를 이용해서 이래저래 끄적거리는 기록도 공유하려합니다.

 

처음 문제를 보고 든 생각은 그냥

a 배열은 순방향 정렬, b 배열은 역방향 정렬을 한 후에 그 둘을 더하면 되는게 아닌가?

라는 생각이 들었습니다.

 

그러나 백준의 조건으로 배열 B를 재정렬하지 말라고 해서 살짝 당황했는데 
혹시 이 조건을 무시하고 제출했을 때 되나? 하고 해봤는데 됩니다!ㅋㅋㅋ

 

다른 분들 블로그를 찾아보는데도 다들 이 방식으로 풀어서 띠용했네요!

 

같이 스터디하는 분 생각에 따르면

재배열하지 말라고는 했지만 재배열 안된 B에 A를 끼워맞춰서 넣는거나
A는 오름차순(또는 내림차순) B는 내림차순(또는 오름차순) 으로 하는거나
덧셈의 교환법칙에 의하면 결국 같은 결과니까 막지 않는 것 같다고 하셨습니다

 

https://github.com/mjung1798/algorithm_Java

mjung1798/algorithm_JAVA

package com.jyami;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Main_1026 {


    public static void main(String args[]) {

        Scanner scanner = new Scanner(System.in);
        int arrSize = scanner.nextInt();
        List<Integer> a = new ArrayList<>();
        List<Integer> b = new ArrayList<>();
        int sum = 0;

        for (int i = 0; i < arrSize; i++) {
            a.add(scanner.nextInt());
        }

        for (int i = 0; i < arrSize; i++) {
            b.add(scanner.nextInt());
        }

        a.sort(Comparator.naturalOrder());
        b.sort(Comparator.reverseOrder());

        for (int i = 0; i < arrSize; i++) {
            int mult = a.get(i) * b.get(i);
            sum += mult;
        }

        System.out.println(sum);

    }

}

Starting this semester, I kicked off an algorithm study group called Imergoroup!

We solve 3 problems per week and plan to upload on Tuesdays, Thursdays, and Saturdays.

To be honest, I still haven't been able to solve problem 1415, which was Tuesday's assignment ㅠㅜ

 

For now, let me share my experience with problem 1026, which was this Thursday's assignment.

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

Problem 1026: Treasure

 

I also want to share my scribbled notes from my iPad.

 

My first thought when I saw the problem was simply:

Can't I just sort array A in ascending order and array B in descending order, then add them up?

That's what came to mind.

 

However, the problem on Baekjoon says not to rearrange array B, which threw me off a bit.
I tried submitting while ignoring that condition, and guess what — it worked! lol

 

When I looked at other people's blogs, everyone solved it the same way, which was surprising!

 

According to one of my study group members,

even though it says not to rearrange B, fitting A into the non-rearranged B, or
sorting A in ascending (or descending) order and B in descending (or ascending) order —
by the commutative property of addition, the result is the same, so they probably don't bother blocking it.

 

https://github.com/mjung1798/algorithm_Java

mjung1798/algorithm_JAVA

package com.jyami;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Main_1026 {


    public static void main(String args[]) {

        Scanner scanner = new Scanner(System.in);
        int arrSize = scanner.nextInt();
        List<Integer> a = new ArrayList<>();
        List<Integer> b = new ArrayList<>();
        int sum = 0;

        for (int i = 0; i < arrSize; i++) {
            a.add(scanner.nextInt());
        }

        for (int i = 0; i < arrSize; i++) {
            b.add(scanner.nextInt());
        }

        a.sort(Comparator.naturalOrder());
        b.sort(Comparator.reverseOrder());

        for (int i = 0; i < arrSize; i++) {
            int mult = a.get(i) * b.get(i);
            sum += mult;
        }

        System.out.println(sum);

    }

}