본문 바로가기

Greedy79

[자바] 백준 12034 - 김인천씨의 식료품가게 (Large) (boj java) 문제 : boj12034 정상가와, 정상가의 75%인 할인가가 n 쌍 존재한다. 그리고 문제 조건으로 '정답은 단 하나만 존재하는것이 보장되어 있음'라고 했으므로 정답을 찾으려면 단순히 생각해서 모든 경우를 살펴봐서 그 중 모든 정상가-할인가 쌍이 맞아떨어지는 경우를 찾으면 될 것이다. 하지만 잘 생각해보면 결국 할인가는 정상가보다 언제나 클 것이다. 따라서 주어진 값들 중 가장 큰 값은 할인가가 될 수 없으며 무조건 정상가이다. 따라서, 큰 값부터 정상가로 생각해 할인가를 찾아나갈 경우, 매번 남은 값들 중 가장 큰 값은 정상가일 수 밖에 없다. 정리하자면 오름차순으로 입력이 들어오므로, 마지막 값부터 시작해서 점차적으로 내려오면서 아직 존재하는 값이라면 무조건 정상가이고, 해당 값과 그 할인가를 제외.. 2022. 6. 23.
[자바] 백준 12981 - 공 포장하기 (boj java) 문제 : boj12981 당연히 3개씩 넣는게 가장 좋으며, 그게 안된다면 2개씩, 그것도 안된다면 1개씩이라도 넣으면 된다. 이건 당연한건데 문제는 박스에 들어가는 공의 색은 모두 다르거나, 모두 같아야 한다는 제약때문에 순서를 잘 정해야 한다. 내 경우 이하의 로직으로 풀었다. 1. 우선 가능한 만큼 모두 다른색으로 3개를 박스에 넣는다. (따라서 정렬 후, 가장 낮은 값을 나머지 2개에서 빼줬다.) 2. 이제 3개씩 넣을 수 있는 방법은 모두 같은 색으로 3개를 넣는 방법 뿐이다. 따라서 남은 2개의 색상은 각각 3개씩 가능한 만큼 넣어준다. 3. '2'에서 남은 공운 1개 아니면 2개일 것이다(3개씩 넣었으므로). 이 때 가능한 경우는 다음과 같다. 3.1 둘다 남은게 0개인 경우 -> 모두 3개.. 2022. 5. 8.
코드업 4040 자바 - 펜션 (CodeUp 4040 java) 문제 : CodeUp4040 어차피 중간에 하루라도 지낼 수 없다면 조건이 만족되지 않는다. 따라서 s부터 시작해서 매번 가장 길게 지낼 수 있는 방에서 지내면 된다. 그러다가 지낼 수 없는 날이 되면 -1, t 이상이 됬다면 변경 횟수를 출력하면 된다. 증명은 간단한데, 매번 가장 길게 지낼 수 있는 방이 아닌 다른 곳에 묵었을 때 더 이득이 되는 경우가 있다면 위의 추론이 틀린 것이다. 하지만 더 짧은 기간 지낼 수 있는 방을 고르더라도 동일한 변경횟수까진 나와서 더 낮은 변경 횟수가 될 수 없음은 직관적으로 알 수 있다. 따라서 그리디하게 선택하면 된다. 그럼 해당하는 날에 어느 방이 가장 길게 묶을 수 있는 방인지 어떻게 알 수 있을까? 이건 날을 거꾸로 진행하면서 몇 일을 지낼 수 있는지 pre.. 2022. 4. 18.
백준 1337 자바 - 올바른 배열 (boj 1337 java) 문제 : boj1337 문제 분류는 정렬과 투 포인터 있긴한데, 내 경우엔 그냥 정렬 없이 그리디로 풀었다. 어떠한 수를 추가할 생각을 하는 것 보다는 그냥 추가해야될게 있던 없던 있다고 치고 해봤을 때, 원래 존재하던게 몇 개 있었는지 확인해 보는 것이 더 간단한 방식일 것이다. 그러니깐 그냥 해당 배열에 있는 값을 HashSet에 모두 넣어서 O(1)로 원하는 수를 찾을 수 있도록 해두고, N개의 수에서 현재 보고 있는 원소의 값을 a라고 하자. 그럼 모든 N개의 a값에 대해 a, a+1, a+2, a+3, a+4를 해시셋에서 확인한다. 그럼 존재하지 않는게 몇갠지 알 수 있다. 그 값 중 가장 작은게 답이다. 예를들어 '예제 입력 4'를 보자. 7 6 1 9 5 7 15 8 이걸 다음과 같이 구해볼.. 2022. 4. 3.
백준 16496 자바 - 큰 수 만들기 (boj 16496 java) 문제 : boj16496 당연한거지만 앞에 올수록 더 전체값이 커질만한 순서대로 정렬한 후, 출력해주면 되는 문제이다. 그 정렬 규칙만 잘 정하면 된다. 케이스1 - 예를들어 9와 89999999가 있다. 직관적으로 자리수와 정렬 규칙은 관계가 없음을 알 수 있다. 둘 중 작은 길이의 숫자까지 비교해서 그 중 다른 숫자가 있다면 쉽게 규칙을 정할 수 있다. 이 경우 9를 먼저 놓는것이 당연히 이득이다. 케이스2 - 그럼 98와 98999이 있다면 어떨까? 직관적으로 98999를 먼저 두는 것이 이득임을 알 수 있다. 이 경우는 '케이스1'로는 판단할 수 없는 경우이다. 그렇다면 자리수가 다르면서, 둘 중 작은 자리수까지 비교해도 비교가 안되는 경우를 어떻게 판단할지가 관건임을 알 수 있다. 내 경우 규칙.. 2022. 3. 30.
백준 1417 자바 - 국회의원 선거 (BOJ 1417 JAVA) 문제 : boj1417 1. 시뮬레이션을 돌리자! 이 문제를 만족시키기 위해서 어떻게 해야할지부터 생각해보자. 다솜이가 처음 얻은 듣표수를 a라고 하겠다. 그럼 그 나머지 득표수들을 -시키면서, a를 +시켜나갈 때 나머지 득표수 중 가장 큰 득표수보다 a가 커지면 된다. 그렇다면 중요한 요소는 나머지 득표수 중 가장 큰 득표수이다. 이걸 max라 하겠다. 결국 매번 max값을 -1 시키고, a를 +1 시켜나가면 원하는 답을 구할 수 있다. 예를들어 다음의 경우를 보자. 4 1 3 3 4 답을 찾는 과정은 다음과 같다. 매번 max값을 찾고(빨간색으로 나타냈다), 해당 값을 -1 시키고 a를 +1 시킨다. 그러다가 max1) pq.add(Integer.parseInt(br.readLine())); int .. 2022. 3. 24.
백준 17756 자바 - Kieszonkowe (BOJ 17756 JAVA) 문제 : boj17756 우선 NIESTETY 를 출력해야 하는 경우부터 살펴보자. 결국 n개에 대해 가장 큰 짝수를 구해야 하는데, 짝수로 만들 수 없다는 얘기는 n이 1개였고, 그 한개가 홀수인 경우 밖에 없다. 이제 전체 로직을 살펴보자. 짝수를 만들 수 있는 경우를 살펴보면 된다. 우선 짝수+짝수는 당연히 짝수이다. 홀수+홀수도 역시 짝수이다. 따라서 짝수는 그냥 넘어가면 되고, 홀수는 홀수인 것이 짝수개 있다면 짝수로 만드는데 문제가 없다. 이제 문제는 홀수가 홀수개 있는 경우인데, 이 때는 한 개의 수를 제외해야 한다. 당연히 가장 작은 홀수를 제거하는 것이 이득일 것이다. 최종적으로 전체 로직을 살펴보면 다음과 같다. 코드 : github import java.io.BufferedReader.. 2022. 3. 24.
[자바] 프로그래머스 - 체육복 [코딩테스트 연습 Lv1] 문제 : programmers-체육복 1. '여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.' 부분부터 처리해야 한다. lost와 reserve에 동시에 포함되는 항목이 있다면 양쪽에서 제거해서, '2' 이후의 로직에 영향을 끼치면 안된다. 2. +-1인 학생한테 체육복을 빌릴 수 있으므로 무지성으로 lost 기준으로 +-1 학생한테 빌릴 수 있으면 바로 빌리고, reserve에서 제거하면 된다. 뭐 오름차순으로 -1인 학생부터 빌리고 이런 과정이 필요 없다. 만약 +-2 이상으로 빌릴 수 있었다면 누가 누구한테 빌리는지에 따라 빌릴 수 있는 학생의 수가 변경될 것.. 2022. 3. 23.
백준 21356 자바 - Hundraelva kronor (BOJ 21356 JAVA) 문제 : boj21356 간단한 그리디 문제이다. 최소의 지폐 수를 구해야 하므로, 큰 값을 가지는 지폐부터 나누어나가면 된다. 문제의 제한에 맞는 1로 만들 수 있는 가장 큰 수부터 (111,111,111) n이 0이 될 때까지 한 자리씩 줄여나가면서(111,111,111 -> 11,111,111 -> 1,111,111 -> ... -> 1) 나눈 몫이 결국 출력해야 하는 지폐의 수이다. 그리고 매번 남은 나머지가 남은 지폐의 양이 된다. 결국 최종적으로는 1로 나누게 되므로 답을 못구하는 경우는 없다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private void so.. 2022. 3. 9.
백준 20115 자바 - 에너지 드링크 (BOJ 20115 JAVA) 문제 : boj20115 어떻게 해야 최대치가 될까? '/2'를 통해 줄어드는 양을 최소화 하면 된다. 그렇다면 일단 합친 값에 대해 추가로 '/2' 연산을 하면 안된다는 점을 알 수 있다. 예를들어 A, B, C가 있을 때 A에 B를 부어서 A가 A+B/2 가 됬다 해보자. 이 용액을 추가로 C에 부어버린다면 C = C + A/2 + B/4가 되는 셈이다. 즉 이미 합쳐진 용액은 더이상 건들지 않는것이 이득이다. 그럼 N개의 용액 중 1개에다가 나머지를 전부 부어버리는 것이 이득임을 알 수 있고, 전체 수치가 최대가 되려면 가장 큰 값을 가지는 용액에다가 나머지 전부를 부어야 함을 알 수 있다. 따라서 단순히 매번 입력을 받으면서 그 중 max 값을 찾고, 모든 용액을 더한다(sum). 최종적으로 답은.. 2022. 2. 24.

티스토리툴바