2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로..
알고리즘 문제를 풀다보면 2차원 배열에서 특정 기준으로 이동을 해야할 때가 있다. map[x][y] : 2차원배열 특성 상 x는 위,아래 / y는 왼쪽,오른쪽 움직임을 관여 // 위, 아래, 왼쪽, 으른쪽 이동 -> 문제 요구사항(조건)에 따라 변할 수 있음 int[] dx = {-1, 1, 0, 0}; int[] dy = {0, 0, -1, 1}; // 현재 좌표 기준으로 위, 아래, 왼쪽, 으른쪽을 다 방문처리 해야한다고 가정 for(int i=0; i
2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 ..
코딩테스트 문제를 풀다보면 정렬을 해야하는 경우가 종종 있는데, Arrays.sort()함수는 배열을 기준으로 동작하는 함수인데 컬렉션을 적용하는 실수를 하곤 한다. 컬렉션을 정렬하기 위해서는 Collections.sort()함수를 써야하며 제네릭 타입으로 래퍼클래스를 받는 경우가 아니라면, 혹은 직접 정렬 기준을 정하고 싶을때는 정렬 기준을 구현해 주어야 한다.(Comparable 과 Comparator 인터페이스를 이용하는 방법이 있다.) 이번 포스트에서는 배열의 정렬과 컬렉션 정렬에 대해 정리하려고 한다. 1. Arrays.sort() (오름차순) Arrays.sort(str); // 새로운 배열을 반환하는 것이 아닌 기존의 참조변수 배열을 정렬 정렬이 되는 기준은 오름차순으로 숫자 > 대문자 > ..
코딩 테스트 문제에서 dfs(depth-first-search, 깊이우선탐색), bfs(breate-first-search, 너비우선탐색)알고리즘 문제가 빈번하게 등장한다. 이러한 알고리즘들은 보통 그래프 이론을 통해 구현한다. 그래서 그래프 이론 개념에 대해 정리하고 그래프이론을 통해 dfs, bfs를 구현 해보려고 한다. 해당 포스터에서 dfs, bfs의 개념은 다루지 않는다. 간단하게 정리하고 넘어가자면 dfs는 스택, 재귀함수를 통해 구현할 수 있고, bfs 큐를 이용하여 구현할 수 있다. 1. 그래프(graph) 수학적 정의로 그래프는 객체들의 쌍들이 서로 연관되어 객체의 집합을 이루는 구조를 의미합니다. 쉽게 설명하면 사물이나 추상적인 개념간의 연결 관계를 표현한 것이라고 할 수 있습니다. 도..
앞서 [#4]장에서 자바 가상머신에 대해 정리 한 적이 있다. 정리하자면 1. 자바 가상머신은 운영체제 위에서 실행되는 하나의 프로그램이다. 2. 자바 프로그램은 자바 가상머신 위에서 실행되는 프로그램이다. 이후 자바 가상머신이 메모리를 관리하는 방법에 대해 정리하려고 한다. 메소드 영역 스택 영역 힙 영역 위 그림에서 보이듯이 자바 가상머신은 메모리 공간을 크게 세 개의 영역으로 나눠서 관리한다. 간단하게 정리하면 다음과 같다. 메소드 영역(Method Area) : 클래스의 바이트 코드, static 변수 스택 영역(Stack Area) : 지역변수, 매개변수 힙 영역(Heap Area) : 인스턴스 메소드 영역(Method Area) 소스파일을 컴파일러가 컴파일 하면 생성되는, 자바 가상머신이 실행..
자바언어로 프로그래밍을 처음 공부했을 때 접했던 주제이지만, 시간이 지나면서 까먹게 되었다. 그 뒤로 자바 언어의 실행 원리에 대해 인지 하지 못한 채 프로그래밍을 해왔다. 물론 실행의 원리를 모른다고 해서 개발을 못하는 것이 아니지만 문득 자바라는 언어의 실행 원리가 궁금해서 책을 찾아보게 되었다. 자바 프로그램의 실행 구조와 자바 가상머신 아래는 일반적인 프로그램의 실행 구조이다. Program Operating System Hardware 하드웨어 기반으로 운영체제가 동작하고, 그 위에서 프로그램의 실행되는 구조이다. 아래는 자바 프로그램의 실행 구조이다. Program Java Virtual Machine Operating System Hardware 하드웨어 기반으로 운영체제가 동작하고, 운영체..
10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 예제 입출력 예제 입력 예제 출력 10 5 2 3 1 4 2 3 5 1 7 1 1 2 2 3 3 4 5 5 7 풀이 정렬 알고리즘은 여러가지 방법..
1427번: 소트인사이드 첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자. 입력 첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다. 예제 입출력 예제 입력 예제 출력 2143 4321 풀이 이번 문제는 하나의 수를 입력받아서 한글자 단위로 나눠서 정렬 후 출력해주면 끝난다. 풀이방법은 첫번째로 수학적원리를 이용한 방법과 두번째로 문자열을 한 문자로 나눠서 배열로 반환해주는 toCharArray()메소드를 이용한 방법으..
2751번: 수 정렬하기 2 (acmicpc.net 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 예제 입출력 예제 입력 예제 출..
2750번: 수 정렬하기 (acmicpc.net) 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 예제 입출력 예제 입력 예제 출력 5 5 2 3 4 1 1 2 3 4..
정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다. 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다. 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(binary search)가 가능해진다. 이진 탐색은 정렬이 되어있어야 사용할 수 있기 때문이다. 즉 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하다. 학습 목표 선택 정렬(Selection Sort) 삽입 정렬(Insert Sort) 큌 정렬(Quick Sort) 계수 정렬(Count Sort) 버블 정렬(Bubble Sort) 1. 선택 정렬(Selection Sort) 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다. 선택 정렬은 N번 만큼 ..
알고리즘 문자열 관련 문제를 풀다보면 문제조건에서 대문자와 소문자를 구분하지 않는 조건을 주어질 때가 있다. 이럴때는 대문자든 소문자는 하나를 정해서 바꿔놓고 알고리즘을 짜면 두경우를 모두 고려하지 않아도 되므로 손쉽게 문제에 접근할 수 있다. 1. toUppderCase() 문자열을 대문자로 바꿔서 반환하는 함수이다. String str = "Hellow World"; System.out.println(str.toUpperCase()); // HELLOW WORLD 출력 2. toLowerCase() 문자열을 소문자로 바꿔서 반환하는 함수이다. String str = "Hellow World"; System.out.println(str.toLowerCase()); // hello world 출력
1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net 문제 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. 입력 첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어진다. 주어지는 단어의 길이는 1,000,000을 넘지 않는다. 출력 첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다. 단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는 ?를 출력한다. 예제 입출력 예제 입력 예제 출력 Mississipi ? zZa ..
10809번: 알파벳 찾기 각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출 www.acmicpc.net 문제 알파벳 소문자로만 이루어진 단어 S가 주어진다. 각각의 알파벳에 대해서, 단어에 포함되어 있는 경우에는 처음 등장하는 위치를, 포함되어 있지 않은 경우에는 -1을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 단어 S가 주어진다. 단어의 길이는 100을 넘지 않으며, 알파벳 소문자로만 이루어져 있다. 출력 각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다...
문자열 관련 문제를 풀다보면 문자열에서 특정 문자를 찾거나 위치를 기반으로 문제를 해결해야 하는 경우가 있다. indexOf() 문자열에서 해당 문자 혹은 문자열의 인덱스를 반환해주는 함수이다. 만약 해당 문자가 문자열에 없으면 -1을 리턴한다. String s = "Hello welcome to the this place"; s.indexof("welcome");// 문자열 검색 s.indexof("t");// 단어 검색 s.indexof("welcome", 10);// 10번째 index부터 문자열 검색 s.indexof("t", 10);// 10번째 index부터 단어 검색 contains() 문자열에서 해당 문자 혹은 문자열이 포함되어있는 여부를 boolean값으로 반환해주는 함수이다. Strin..
1152번: 단어의 개수 첫 줄에 영어 대소문자와 띄어쓰기로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 띄어쓰기 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 www.acmicpc.net 문제 알파벳 소문자로만 이루어진 단어 S가 주어진다. 각각의 알파벳에 대해서, 단어에 포함되어 있는 경우에는 처음 등장하는 위치를, 포함되어 있지 않은 경우에는 -1을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 단어 S가 주어진다. 단어의 길이는 100을 넘지 않으며, 알파벳 소문자로만 이루어져 있다. 출력 각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약,..
문자열을 배열과같이 인덱스로 접근하여 해당 문자를 가져오는 방법이다. 또한 연산을 하게되면 해당 문자의 아스키코드값을 반환한다. 다음 예제는 입력값의 합을 구하는 예제이다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); String a = in.next(); in.close(); int sum = 0; for(int i = 0; i < N; i++) { sum += a.charAt(i)-'0'; } System.out.print(sum); } } 숫자에 대한 char의 아스키 코드는 다음과 같..
11720번: 숫자의 합 첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다. www.acmicpc.net 문제 N개의 숫자가 공백 없이 쓰여있다. 이 숫자를 모두 합해서 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다. 출력 입력으로 주어진 숫자 N개의 합을 출력한다. 예제 입출력 예제 입력 예제 출력 1 1 1 5 54321 15 25 7000000000000000000000000 7 11 10987654321 46 풀이 본 문제는 자바에서 문자열을 자를 수 있는 방법 또는 문자열을 문자로 나눠서 아스키코드를 이용하여 int형으로 바꿔서 푸는 방법등 다양..
알고리즘 문제를 풀다보면 문자열을 잘라서 사용해야 하는 경우가 있다. 자바에서 문자열을 자르는 방법중에 대표적인 방법으로 Substring과 Split함수가 있다. 둘의 차이점은 Substring은 인덱스를 기준으로 문자열을 잘라 문자열을 반환하고, Split은 사용자가 지정한 특정 기준으로 문자열을 잘라 배열로 반환한다. 1. Substring 사용법 //사용법 String.substring(start) //문자열 start위치부터 끝까지 문자열 자르기 String.substring(start,end) //문자열 start위치 부터 end전까지 문자열 발췌 //예제 String str = "ABCDEFG"; //대상 문자열 /*A=0 B=1 C=2 D=3 E=4 F=5 G=6의 index를 가진다.*/..
자바에서 배열을 지정한 값으로 초기화하는 방법이다. 1. 1차원 배열 int[ ] 채우기 public static void main(String[] args) { int[] a = new int[5]; Arrays.fill(a, 100);//100으로 일괄 초기화 for(int i : a) { System.out.print(i +" "); } } 2. 2차원 배열 int[ ][ ]채우기 public static void main(String[] args) { int[][] b = new int[5][5]; for(int i = 0; i < b.length; i++) { Arrays.fill(b[i], 100); } //출력 for(int[] i : b) { for(int j : i) { System.ou..
사용 이유 String은 불변(immutable)객체라고 한다. String str1 = "abc";, String str2 = "def" 2개의 String객체가 있을 때, str1+str2와 같은 연산을 하게되면 새로운 String을 생성한다. String객체와 String객체를 더하는 행위는 메모리 할당과 메모리 해제를 발생시키며 더하는 연산이 많아진다면 성능적으로 좋지 않다. StringBuilder 그래서 나온 것이 StringBuilder이다. StringBuilder는 String과 문자열을 더할 때 새로운 객체를 생성하는 것이 아니라 기존의 데이터에 더하는 방식을 사용하기 때문에 속도도 빠르며 부하가 적다. 따라서 긴 문자열을 더하거나 더하는 상황이 반복되는 경우에 StringBuilder..
1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다. 1 2 3 4 5 6 7 8 9 10 11 int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); } } fibonacci(3)을 호출하면 다음과 같은 일이 일어난다. fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다. fibon..
9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 예제 입력 예제 입력 예제 ..
1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 예제 입출력 예제 입력 예제 출력 2 1 10 3 힌트 10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다. 풀이 이번..
2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다. 상근이가 ..
1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보..
11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,0..
11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다..