백준 11399번 자바

문제

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

11399번: ATM

1. 삽입정렬을 이용해 문제를 해결했다.

삽입정렬이란 예를들어 아래 파란식 글씨 부분들이 정렬된 부분이고, 빨간색 글씨부분이 현재 인덱스일때 현재 인덱스의 값을 정렬된부분에 삽입을 하는 것이다.

1	2	3	4	5
13	15	12	17	16

12는 13보다 작은 수이기때문에 가장 앞에 삽입되고 나머지 값들은 한칸씩 뒤로 이동이 된다.

3	1	2	4	5
12	13	15	17	16

값이 한칸씩 뒤로 밀려 저장되는 것만 주의하면 크게 어렵지 않다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main11399 {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] P = new int[N];
		int sum = 0;
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for (int i=0; i<P.length; i++) {
			P[i] = Integer.parseInt(st.nextToken());
		}
		
		for (int i=1; i<N; i++) {
			for (int j=0; j<i; j++) {
				if (P[i] < P[j]) {
					int temp = P[i];
					
					for (int k=i-1; k>=j; k--) {
						P[k+1] = P[k];
					}
					
					P[j] = temp;
					break;
				}
			}
		}
		
		for (int i=1; i<N; i++) {
			P[i] = P[i] + P[i-1];
			sum += P[i];
		}
		
		System.out.println(sum + P[0]);
	}
}

 

정리 : 푸는 방법은 여러가지겠지만 삽입정렬에 대해 공부한다는 마음으로 구현을 했다. 이전까지는 정렬관련된 문제를 많이 풀어보지 않았는데 이번 기회에 정렬쪽을 확실하게 공부하고 가야겠다.