막내의 막무가내 프로그래밍 & 일상

https://www.acmicpc.net/problem/9237 9237번: 이장님 초대 입력은 두 줄로 이루어져 있다. 첫째 줄에는 묘목의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 각 나무가 다 자라는데 며칠이 걸리는지를 나타낸 ti가 주어진다. (1 ≤ ti ≤ 1,000,000) www.acmicpc.net 백준 그리디 유형에서 9237번 이장님 초대라는 문제를 풀어봤습니다. ㅎㅎ 그리디 유형은 코드는 간단한데 생각을 빨리하는게 역시 중요한 것 같습니다 주석으로 설명은 대체합니다. [Java] import java.util.Arrays; import java.util.Collections; import java.util.Scanner; public class Main { p..

https://www.acmicpc.net/problem/14659 14659번: 한조서열정리하고옴ㅋㅋ 첫째 줄에 봉우리의 수 겸 활잡이의 수 N이 주어진다. (1 ≤ N ≤ 30,000) 둘째 줄에 N개 봉우리의 높이가 왼쪽 봉우리부터 순서대로 주어진다. (1 ≤ 높이 ≤ 100,000) 각각 봉우리의 높이는 중복 없이 www.acmicpc.net 백준 그리디 유형의 한조서열정리하고옴ㅋㅋ 문제를 풀어봤습니다. 간단한 그리디 유형의 문제였는데 가독성이 조금 안좋은 것 같습니다.. 풀이는 다음과 같습니다. [Java] import java.util.Scanner; public class Main { private static int answer = Integer.MIN_VALUE; public static..

https://www.acmicpc.net/problem/11497 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 백준 11497 통나무 건너뛰기 문제를 풀어봤습니다. 그리디 유형의 문제였습니다. 최소의 난이도를 가진 둥근 모양의 통나무 배치를 하기 위해서는 통나무를 양 옆으로 작은것들로 시작하여 점점 가운데로 올 수록 크게 배치하면 최소의 난이도를 만들 수 있습니다. 풀이는 다음과 같습니다. [Java] import java.util.Arrays; import java.util.Scanner; public..

https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 백준 그리디 유형에서 보물이라는 문제를 풀어봤습니다. A와 B 배열의 인덱스 곱의 합이 최솟값이 나와야하는데 A만 재배열이 가능하고 B는 불가능합니다. B가 재배열이 불가하다는 말에 꽂히지말아야합니다. A와 B를 오름차순으로 정렬한다음에 A의 가장 작은값과 B의 가장 큰 값 인덱스들을 서로 곱해주는게 최소의 S결과가 나오게됩니다. 풀이는 다음과 같습니다. [Java] import java...

www.acmicpc.net/problem/10162 10162번: 전자레인지 3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 www.acmicpc.net 백준에서 그리디 유형의 전자레인지 문제를 풀어봤습니다. ㅎㅎ 3가지의 시간초 버튼을 가진 전자레인지로 정해진 시간초(T)를 최소한의 버튼 누르는 횟수로 정확하게 요리할 수 있는지 구하는 문제였습니다. 풀이는 다음과 같습니다. [Java] import java.util.Scanner; public class Main { public static void main(String[] args) { Scanne..

www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 백준 그리디 단계별풀기에서 마지막 문제를 안풀어서 이번에 풀어봤습니다. 문제에 대해 간략히 설명하면, 기름값이 다른 도시들이 있고 각 도시는 일렬로 다른거리로 연결되어 있습니다. 도시에 도착했을때 기름*km수 만큼 기름을 채울 수 있다. 마지막도시까지 가는데 필요한 최소 기름값을 출력하면 됩니다. 풀이 방법은 기름값이 이전 도시보다 더 낮은 경우 더 낮은 기름값으로 다음 도시까지의 거리만큼 기름을..

www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 백준 그리디유형의 문제인 뒤집기를 풀어봤습니다. ㅎㅎ 연속된 숫자를 한번에 뒤집을 수 있는데요 (0 or 1) 최소한으로 뒤집어서 모두 같은 숫자를 만들어야합니다. 풀이방법은 0과 1의 연속된 숫자의 묶음이 더 적은 쪽의 묶음의 개수를 답으로 출력해주면 됩니다. 풀이는 다음과 같습니다. [Java] import java.util.Scanner; class Main { private static String S;..

www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 백준 그리디 유형 분류에 있는 문제이자 우선순위큐를 사용하여 풀 수 있는 문제입니다. 시작하는 시간과 끝나는 시간을 알려주는데 최대 몇개의 강의실이 필요한지 구하는 문제였습니다. 먼저 시간이 정렬되어서 입력이 안오므로 빠른시작시간순과 빨리 끝나는 순서로 정렬을 해줍니다. 그 후 우선순위큐를 사용하여 최대 몇개의 강의실이 필요한지 계산합니다. 코드를 보면 이해할 수 있으니 자세한 내용은 생략하도록 하겠습니다. 풀이는 다음과 같습니다. [Java] import ..

www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 모 코테에서 나온 문제와 똑같다. 시간을 좀 잡아먹었던 문제입니다. ㅂㄷ 풀이는 다음과 같습니다. [Java] import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; class Main { public static void main(String[] args) { Scanner sc = new Scann..

www.acmicpc.net/problem/2847 2847번: 게임을 만든 동준이 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어 www.acmicpc.net 하루에 시간이 없어도 한문제씩은 풀려고 했는데 요즘 못풀고 있습니다. 감이라도 안잃게 그리디 문제 골라서 풀어봤습니다. 주석으로 설명되는 간단한 문제였습니다. [Java] import java.util.Scanner; class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextIn..

www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 백준 그리디 유형의 문제입니다. 키가 1인 사람부터 N인 사람까지 차례대로 입력을 받으며 해당 키 사람의 왼쪽에 입력 만큼의 키큰 사람이 왼쪽에 있어야합니다. 다음 블로그에서 설명을 잘해놓았습니다. lipcoder.tistory.com/entry/%ED%95%9C-%EC%A4%84%EB%A1%9C-%EC%84%9C%EA%B8%B0-%EB%B0%B1%EC%A4%80-1138%EB%B2%88 한 줄로 서기 ..

www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 백준 1436 영화감독 숌 단계별풀기 브루트포스 마지막 문제 입니다. 숫자를 1씩 증가시켜가며 666이 포함된 숫자를 찾으면 오름차순으로 숌영화네임을 찾을 수 있습니다. 풀이는 다음과 같습니다. [Java] import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(Sy..

www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 백준 그리디 단계별풀기 마지막 문제인 잃어버린 괄호 문제입니다. 괄호를 추가해서 +,- 수식을 최솟값을 만들어야 합니다. - 가 붙어 있다면 처음거는 더하고 그 뒤 부터는 쫙 뺴주면 됩니다. - 뒤에 -가 나올때까지 + 들을 괄호묶어서 최대값을 뺴줍니다. 예시를 남깁니다. 1 + 2 + 3 + 4 - 5 + 6 - 8 - 9 + 10 + 11 -> 1 + 2 + 3 + 4 - ( 5 + 6 ) - ( 8 ..

www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 백준 그리디 단계별풀기를 하고있습니다. 걸리는 시간의 최솟값은 오름차순일때입니다. [Java] import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.ne..

https://programmers.co.kr/learn/courses/30/lessons/42884?language=java 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 프로그래머스 LEVEL3 의 단속카메라 문제를 풀어봤습니다. ㅎㅎ 풀이 방법은 다음과 같습니다. 1. 종착지점을 기준으로 오름차순 정렬합니다. 2. 반복문을 통해 routes를 갖고옵니다. 3. 카메라 설치 지점과 현재 route의 진입 지점과 비교하여 카메라 설치 지점에 커버되는 곳이면 PASS 아닌 경우는 카메라 설치 지점을 현재 route 의 종착 지점으로 변경해주고 카메라 설치 개수가 한개 늘어납니다. 풀이는 다음과 같습니다. [Jav..