알고리즘/백준 풀이(그리디)

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 위 문제는 최대한 진행할 수 있는 회의의 수를 출력하는 문제인데 회의 시간이 겹치지 않도록 해야한다. 예를 들어 1 4 5 7 이런 식으로 한 시간 차이로 진행할 수 있으며 1 4 4 4 4 5 이런 식으로 회의 시작 시간과 종료 시간이 같은 경우에도 가능하며 이 경우 출력은 3이 된다. ※위 문제 핵심 1. 종료시간을 기준으로 오름차순 정렬한다. 2. 종료시간이 같고 시작 시간이 다른 경우는 또 시작시간을 기준으로 오름차순 해야한다. ▶코드 import java.util.*; import java.io.*; p..

https://www.acmicpc.net/problem/1417 1417번: 국회의원 선거 첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어온다. N은 50보다 작거나 같 www.acmicpc.net 다음 문제는 주어진 수들 중 최대값을 찾아 arr[0]의 값과 +1, -1 씩 교환하고 최대값이 arr[0] 으로 되기 전까지 다시 최대값을 찾아 이 계산을 반복한다. ▶코드 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { B..

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

https://www.acmicpc.net/problem/1105 1105번: 팔 첫째 줄에 L과 R이 주어진다. L은 2,000,000,000보다 작거나 같은 자연수이고, R은 L보다 크거나 같고, 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 예제 800 899 - 출력 : 1 800 900 - 출력 : 0 80000 89999 - 출력 : 1 80000 8131231231 - 출력 : 0 L과 R의 자릿 수가 다르면 8이 안 들어가도 됨 ( 예 : 89 90 이면 8이 안 들어가도 됨 ) L과 R의 자릿 수가 같으면 연속되는 수만큼의 8이 들어가야함 ( 예: 8800 8809 이면 8이 두 개 들어가야함 ) L과 R의 자릿수가 다르면 8이 안 들어가도 되는 수가 ..

https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 이 문제는 배열의 뒷부분부터 계산을 하면 된다. 예를 들어 1 1 3 1 2 이라는 예제가 있을 때 최댓값을 마지막 인덱스인 2로 두고 배열의 뒷 부분부터 2보다 큰 숫자가 나올 때까지 2에서 그 사이의 배열의 값을 빼준다. 즉 2 - 1 = 1 3 - 1 = 2 3 - 1 =2 해서 5 라는 값이 출력되는 것이다. 왼쪽 수는 최댓값을 의미하는 max 변수로 두고 코드를 작성하면 된다..

https://www.acmicpc.net/problem/2847 2847번: 게임을 만든 동준이 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어 www.acmicpc.net 이 문제는 첫 번째 레벨부터 마지막 레벨까지 점수가 순차적으로 상승하도록 만들면 된다. 3 5 5 5 위 예제에서 5 5 5 는 3 4 5 가 되도록 하는데 이 때 첫 번째 5는 -2 , 두 번째 5는 -1 의 계산을 해야하므로 출력은 3이 된다. 어차피 마지막 레벨인 배열의 마지막 부분을 기준으로 한 단계씩 내리면서 점수를 차감해야 하기 때문에 기준이 되는 last 값은 arr[3] → arr..

https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 이 문제는 누수가 발생한 부분에 길이가 N인 테이프를 사용하여 조치할 때 필요한 최소의 테이프 개수를 출력하는 문제이다. 예제에서 4 2 1 2 100 101 은 길이가 2인 테이프이므로 누수 발생 지점인 1과 2, 100과 101 을 총 두 개의 테이프로 막을 수 있다. 코드 import java.util.*; import java.io.*; public class Main { ..

https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 이 문제는 특정 문자를 기준으로 나누는 StringTokenizer 를 통해 풀었다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamRead..

https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 이 문제는 거스름돈을 주는데 동전의 개수가 최소가 되도록 해야한다. 그리고 예외로 거슬러 줄 수 없는 돈이면 -1을 출력해야한다. 예를 들어 7을 입력으로 받으면 5로 딱 떨어지지 않기 때문에 -2 연산을 해줘서 5를 만들어 5로 나누어 떨어지도록 만들어줘야 한다. 11을 입력으로 받으면 5로 떨어지도록 -2 연산을 반복하여 딱 나누어 떨어지도록 만든다. ( 11 → 9 → 7 → 5 → 0 ) ▼코드 import java.io.*; import java.util.*; public class Main { public..

https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 이 문제는 문제 자체를 이해하기 힘들었던 문제이다. 둘째 줄부터의 숫자는 서류, 면접 성적의 순위를 입력한 것이며 이에 선발할 수 있는 최대 인원 수를 출력해야 한다. 예제 입력1 과 같은 예시가 있을 때 먼저 서류 면접이 1등인 사원인 1 4 를 기준으로 비교했을 때 2 3 은 면접 성적이 더 높기 때문에 합격이고 3 2 는 2 3 보다 면접 성적이 더 높기 때문에 합격, ..