[java] 문제 018 (백준 11399)

문제

ATM

 

교재 풀이

import java.util.Scanner;
public class P11399_ATM {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] A = new int[N];
    int[] S = new int[N];
    for (int i = 0; i < N; i++) {
      A[i] = sc.nextInt();
    }
    for (int i = 1; i < N; i++) { //삽입 정렬
      int insert_point = i;
      int insert_value = A[i];
      for (int j = i-1; j >= 0; j--) {
        if (A[j] < A[i]) 
        {
         insert_point = j+1;
         break;
        }
        if(j==0) {
          insert_point = 0;
        }
      }
      for (int j = i; j > insert_point; j--) {
        A[j] = A[j-1]; 
      }
      A[insert_point] =insert_value;
    }
    S[0]=A[0]; //합배열 만들기 
    for (int i = 1; i < N; i++) { 
      S[i] = S[i-1]+A[i];
    }
    int sum = 0; //합배열 총합 구하기
    for (int i = 0; i < N; i++) {
      sum = sum + S[i];
    }
    System.out.println(sum);
  }
}

 

내 풀이) 24.6.9에 풀고 맞음

import java.util.*;
import java.io.*;

public class Main
{
	public static void main(String[] args) throws IOException{
// 		ATM앞에 N명의 사람들이 줄을 서있다.
// 		    사람은 1번부터 N번까지 번호가 매겨져 있으며
// 		    i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.
// 	    사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다
// 	        , P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우
// 	        줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 
// 	        2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분
// 	        시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.
//         돈을 인출하는데 필요한 시간의 합의 최솟값
        
//         첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)
//         둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)
//         첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력
//         입력
//             5
//             3 1 4 3 2
//         출력 
//             32
//         접근법
//             정렬 문제다 
//             합 구간을 사용해라는 메모가 남겨져 있다 
//             그러네. 그냥 오름차순으로 정렬 후 구간 합 쓰면 대충 되겠네
//         슈도 코드
//             n을 입력받음 
//             각 사람의 인출 시간을 입력받음 -> 배열에 
            
//             오름차순 정렬함 
//             인출 시간 배열을 합 배열로 만듦 
            
//             완성된 합 배열의 각 원소를 더해서 정답을 출력한다 
        
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        int n=Integer.parseInt(st.nextToken());
        
        st=new StringTokenizer(br.readLine());
        int[] time=new int[n];
        for(int i=0;i<n;i++){
            time[i]=Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(time);
        
        long[] sum=new long[n];
        sum[0]=time[0];
        for(int i=1;i<n;i++){
            sum[i]=sum[i-1]+time[i];
        }
        
        long ans=0;
        for(int i=0;i<n;i++){
            ans+=sum[i];
        }
        
        System.out.println(ans);
	}
}

 

설명

교재에선 삽입 정렬로 구현했지만

실제 코테에서 이렇게 구현하지 않을테니 말이다.

너무 목매달려 외우고 이해하려 하지 말고 넘어가라.

 

• 삽입 정렬 알고리즘 설명
  • 삽입 정렬은 주어진 배열을 정렬하는 간단한 정렬 알고리즘 중 하나입니다. 이 알고리즘은 배열을 순차적으로 탐색하면서, 각 원소를 적절한 위치에 삽입하여 정렬된 배열을 생성합니다.
  • 주어진 코드를 바탕으로 동작 과정을 설명하겠습니다. 배열 A가 [3, 1, 4, 1, 5]일 때, 삽입 정렬이 어떻게 동작하는지 보겠습니다.
• 요약
  1. 각 i에 대해 A[i] 값을 insert_value로 저장합니다.
  2. insert_value가 삽입될 위치를 결정하기 위해 내부 for문을 실행합니다.
  3. 결정된 위치에 insert_value를 삽입하기 위해, 배열 요소들을 오른쪽으로 이동시킵니다.
  4. insert_value를 결정된 위치에 삽입합니다.
• 코드 설명

for (int i = 1; i < N; i++) { // 삽입 정렬
    int insert_point = i;
    int insert_value = A[i];
    for (int j = i-1; j >= 0; j--) {
        if (A[j] < A[i]) {
            insert_point = j + 1;
            break;
        }
        if (j == 0) {
            insert_point = 0;
        }
    }
    for (int j = i; j > insert_point; j--) {
        A[j] = A[j-1];
    }
    A[insert_point] = insert_value;
}

• 동작 과정
  • 초기 배열 상태: A = [3, 1, 4, 1, 5] / N = 5
• i = 1
  1. insert_point = 1
  2. insert_value = 1
  3. 내부 for문:
     • j = 0: A[0] < A[1] (3 < 1) 조건이 거짓이므로 insert_point = 0
  4. 내부 for문 종료 후:
     • A[1] = A[0] (A는 [3, 3, 4, 1, 5])
  5. A[insert_point] = insert_value:
     • A[0] = 1 (A는 [1, 3, 4, 1, 5])
• i = 2
  1. insert_point = 2
  2. insert_value = 4
  3. 내부 for문:
     • j = 1: A[1] < A[2] (3 < 4) 조건이 참이므로 insert_point = 2로 유지, break
  4. 내부 for문 종료 후:
     • insert_value가 insert_point에 이미 있으므로 변경 없음 (A는 [1, 3, 4, 1, 5])
• i = 3
  1. insert_point = 3
  2. insert_value = 1
  3. 내부 for문:
     • j = 2: A[2] < A[3] (4 < 1) 조건이 거짓
     • j = 1: A[1] < A[3] (3 < 1) 조건이 거짓
     • j = 0: A[0] < A[3] (1 < 1) 조건이 거짓, insert_point = 0
  4. 내부 for문 종료 후:
     • A[3] = A[2] (A는 [1, 3, 4, 4, 5])
     • A[2] = A[1] (A는 [1, 3, 3, 4, 5])
     • A[1] = A[0] (A는 [1, 1, 3, 4, 5])
  5. A[insert_point] = insert_value:
     • A[0] = 1 (변경 없음)
• i = 4
  1. insert_point = 4
  2. insert_value = 5
  3. 내부 for문:
     • j = 3: A[3] < A[4] (4 < 5) 조건이 참이므로 insert_point = 4로 유지, break
  4. 내부 for문 종료 후:
     • insert_value가 insert_point에 이미 있으므로 변경 없음 (A는 [1, 1, 3, 4, 5])
• 최종 배열 상태: A = [1, 1, 3, 4, 5]