BOJ (4) 썸네일형 리스트형 [JAVA] BOJ 11399 ATM 그리디 알고리즘 문제 중에서도 가장 쉬운 문제인 것 같다. 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 찾는 문제인데 단순하게 각 사람의 기다리는 시간이 주어졌을 때 오름차순으로 정렬해서 세우는 것이 최소이다. 왜냐하면 돈을 인출하는데 걸리는 시간이 긴 사람이 앞에 있으면 계속 누적이 되기 때문에 값이 커질 수밖에 없다. 따라서 주어진 배열을 오름차순으로 정렬한 다음 각 요소를 이전 값까지의 누적 값과 더해 새롭게 저장한다. 즉, A(i) = A(i-1) + A(i) 이다. Input에는 BufferedReader 와 Output에는 System.out.println을 사용했다. public class Main { public static void main(String[] args) throw.. [JAVA] BOJ 11047 동전 0 그리디 알고리즘은 탐욕 알고리즘이라 하여 뒤를 생각하지 않고 각 상황에서 최선의 선택만을 하는 알고리즘을 의미한다. 이 문제에서는 예제에서 주어진 4200원을 만들기 위해 4200원보다 작은 것 중 가장 큰 동전을 선택하여 (예제에선 1000원) 개수에 4200/1000 한 것을 더해주고 K = 4200%1000 = 200으로 만들어주어 K가 0이 될 때까지 위의 과정을 반복합니다. 첫 번째 동전의 값은 1이기 때문에 K가 0이 안될 가능성은 없다. Input으로 주어지는 값이 많기 때문에 BufferedReader를 사용했고 출력되는 수는 한 개 밖에 없기 때문에 System.out.println을 사용했다. public class Main { public static void main(String[].. [JAVA] BOJ 1158 요세푸스 문제 원으로 앉아있다는건 배열을 순환한다는 것과 같다. 따라서 배열의 끝에 도착하면 다시 처음으로 돌아가도록 해주는 것이 핵심이다. 또한 K번째 사람을 제거한다는 것은 배열을 순환하면서 K번째를 방문했으면 넘어가도록 구현하였다. 독특한 출력형태로 input은 Scanner로 받고 출력은 BufferedWriter를 사용하였다. public class Main { public static void main(String[] args) throws IOException { Scanner sc = new Scanner(System.in); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); String st = sc.nextLine(.. [JAVA] BOJ 2579 계단 오르기 계단 오르기 문제는 정답 비율이 35% 정도 되는 어려운 문제였다. 꽤나 까다롭고 예상치 못한 부분이 있어서 2일 정도 계속 고민했던 것 같다. 이전 정수 삼각형 문제와 같이 마지막 계단으로 가는데 누적합이 최대가 되는 경로를 찾아 그 최대 누적합을 출력하는 문제이다. 동적 계획법 문제들이 그렇듯 메모이제이션과 점화식을 잘 찾아내면 해결할 수 있지만 이번 포스팅에선 내가 실패했던 케이스와 이를 해결한 과정을 기록하고자 한다. 실패한 케이스 문제의 조건은 세 개이다. 계단은 한 칸 혹은 두 칸씩 오를 수 있으며 연속된 세 개의 계단은 밟지 못하고 마지막 계단은 '반드시' 밟아야 한다. 문제는 이전 정수 삼각형 문제와 비슷하기 때문에 이 역시도 그와 같은 방법으로 DP 배열에 해당 칸까지의 최댓값을 저장해가.. 이전 1 다음
