Problem Solved/BOJ

[BOJ][Java] 11399번 - ATM

문제 백준 11399번 문제: ATM 문제 설명 기다리는 시간의 합을 최소화하는 문제 기다리는 시간의 함을 최소화하기 위해서는 작은 수부터 앞에 와야 한다. 시간 제한이 1초이기 때문에 Arrays.sort()를 통해서 정렬 후 값을 더해 나가면 된다. 0번째 수부터 n번째 수의 합의 합을 구하는 것이 목적인데, for문을 한번만 돌고 싶다. 내가 찾은 방법은 두 가지이다. 인출하는 사람마다 반복해서 더해지는 개수를 세서 더하는 방법 5명이 차례대로 인출을 한다면 1번 사람은 5번 더해진다. 1 1+2 1+2+3 1+2+3+4 1+2+3+4+5위와 같이 첫 번째 사람부터 반복 횟수가 1씩 떨어지기 때문이다. 그래서 이를 계산해서 곱해 주면 된다. for (int time = 0; time < withdr..

[BOJ][Java] 2579번 - 계단 오르기

문제 백준 2579번 문제: 계단 오르기 문제 설명 i번째 계단에 오를 때, 몇 개의 연속한 계단을 올랐는지를 고려하여 부분문제를 정의해봅시다. 성공 코드 import java.util.Scanner; import java.util.stream.IntStream; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int score[] = new int[n+1]; int accu_score[] = new int[n+1]; IntStream.range(1, n+1).forEach(x -> { score[x] = sc.nextInt(); }); s..

[BOJ][Java] 1931번 - 회의실배정

문제 백준 1931번 문제: 회의실배정 문제 설명 가능한 한 많은 구간을 선택하는 문제 일단 그리디 알고리즘은 정해진 기준에서 현재의 가장 최상의 값을 찾아나가는 알고리즘이다. 그럼 회의실배정 문제에서 최상의 값을 찾을 수 있는 기준은 어떻게 잡을 수 있을까? 회의가 끝나는 시간을 최대한 작은 수부터 골라야 한다. 회의 끝나는 시간이 같다면 회의 시작 시간이 작은 수부터 골라야 한다. 성공 코드 import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in..

[BOJ][Java] 11047번 - 동전0

문제 백준 11047번 문제: 동전0 문제 설명 동전의 조건이 특별해서 동적 프로그래밍보다 빠르게 답을 찾을 수 있는 문제 동전의 최소 개수를 찾기 위해서는 큰 수부터 교환될 수 있는지 찾아야 한다. 그래서 입력을 받을 때 n-1번째 인덱스부터 저장시킬 수 있도록 했다. 그래서 50000부터 1까지 루프될 수 있도록 했다. 성공 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int coins[] = new int[n]; for (int i = n-1..

[BOJ][Java] 1932번 - 정수 삼각형

문제 백준 1932번 문제: 정수 삼각형 문제 설명 각 층의 모든 칸마다 최댓값을 저장하면서 동적 계획법으로 푸는 문제 최대값을 찾기 위해서는 이전 열에서 최대값을 더해 나가야 한다. 문제의 예제로 이해를 해보자 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5맨 위의 수인 7은 제일 상단에 위치해 3과 8에 각각 7을 더해주면 된다. 그럼 10과 15가 되어 밑의 수들에게 선택을 받게 된다. 하지만 셋째줄의 맨 처음에 있는 8과 0은 선택의 여지가 없이 위의 수를 더해야 한다. 1은 10과 15 중 큰 수인 15를 선택할 수 있다. 이를 이용하여 큰 수를 축적해 나갈 수 있다. 아래 축적된 수를 보자. 7 10 15 18 16 15 20 25 20 19 24 30 27 26 24가장 밑에 줄에 가장..

[BOJ][Java] 1149번 - RGB거리

문제 백준 1149번 문제: RGB거리 문제 설명 i번째 집을 각각의 색으로 칠할 때, 1~i번째 집을 모두 칠하는 최소 비용으로 부분문제를 정의해봅시다. 설명 추가 예정 성공 코드 import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner s = new Scanner(System.in); int n = s.nextInt(); int[][] rgb = new int[3][n+1]; for (int i = 0; i < n; i++){ rgb[0][i] = s.nextInt(); rgb[1][i] = s.nextInt(); rgb[2][i] = s.nextInt(); } for (int i = 1; i..