[JAVA] 백준 2322 아령

 

 

 

문제분석

정확히 백준 2569 짐정리와 같은 문제이다

solved.ac에 적용이 안되어 이유를 보니, 이 문제와 같은 문제여서 2569가 등록이 안되더라. 그래서 코드 일부(long)만 수정하여 푼 문제로 등록하였다.

해결과정

완벽하게 2569와 같은 문제(long 신경 써 줘야 하는것 제외하면)이다. 따라서 아래 글을 참고하면 된다.

https://chabin37.tistory.com/99

[JAVA] 백준 2569 짐정리

 

문제에서 2^30까지 신경써야 한다고 명시해줬으므로, int 대신 long을 사용하였다.

 

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        long[][] arr = new long[N][2]; // [[짐 무게, 정렬 전 인덱스], ...]

        for(int i = 0; i < N ; i++){
            long lug = Long.parseLong(st.nextToken());
            arr[i][0]=lug;
            arr[i][1]=i;
        }
        Arrays.sort(arr,(a,b)->Long.compare(a[0], b[0]));

        long[] visited = new long[N];
        
        Arrays.fill(visited,0);//0이면 미방문, 1이면 방문

        long price = 0;

        for(int i = 0; i < N; i++){
            if(visited[i]==1){
                continue;
            }else{
                int next = i;
                int cycle = 0;
                while(visited[next]==0){
                    price += arr[next][0];
                    visited[next]=1;
                    next = (int)arr[next][1];
                    cycle += 1;
                }
                price += Math.min(arr[i][0] * (cycle - 2), arr[0][0] * (cycle+1) + arr[i][0]);
            }
        }
        bw.write(String.valueOf(price));
        bw.newLine();
        bw.flush();
        bw.close();


    }
}