본문 바로가기

그리디93

백준 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.
백준 11508 자바 - 2+1 세일 (BOJ 11508 JAVA) 문제 : boj11508 1. 어떻게 최소 비용을 만들 수 있을까? 어차피 중복해서 물건을 구매할 수 없고, 모든 물건을 구매해야 하므로 N개의 물건에 대해 'N/3(내림)'개의 물건만을 2+1 세일로 가격을 빼낼 수 있다. 이걸 변경할 방법이 없으므로, 결국 최대한 비싼 물건을 세일로 빼내는 것이 최소 비용을 만들 수 있는 방법이다. 이 때 특정 3개의 문제를 골랐을 때 이 중 가장 싼 물건의 가격이 빠지는 것이고, 이 '가장 싼 물건'이 최대한 비싼 물건일수록 이득이므로 결국 비싼 물건들부터 고르는 것 말고는 최소 비용을 만들 수 있는 방법이 없다. 즉, 문제 설명에서 나온 7개의 유제품 '10, 9, 4, 2, 6, 4, 3'을 봐보자. 문제에서는 위의 표처럼 그룹지었지만, 세일로 빠지는 가격을 늘.. 2022. 2. 22.
백준 16678 자바 - 모독 (BOJ 16678 JAVA) 문제 : boj16678 1. 문제 이해 결국 단 1번의 Defile로 모두 박탈시키려면 모든 의원의 명예를 1부터 차츰차츰 상승하는 계단형식으로 만들면 된다. 즉, 모든 의원의 명예가 낮은 명예부터 봤을 때 2이상 차이가 나지 않게 하면 된고, 이렇게 만들 때 최소한만 감소시켜서 진행해야 한다. 2. 문제 풀이 1부터 n까지 확인하면서 해당 값을 한명씩 무조건 가지도록 명예를 깎는다면 모든 명예값이 2이상 차이나지 않을 수 있다. 단순히 생각해도 더 낮은 숫자를 만들기 위해서는 애초에 명예가 낮은 의원의 명예를 깎는것이 더 최소한의 횟수로 만들 수 있을 것이다. 따라서 우선 입력으로 들어온 값을 오름차순으로 정렬해보자. 그리고 1부터 1개씩 증가시키며 해당 값에 한명 이상 매칭시켜보자. 예를들어 '예제.. 2022. 2. 21.
백준 12927 자바 - 배수 스위치 (BOJ 12927 JAVA) 문제 : boj12927 얼핏 어렵게 볼 수 있지만, A번 스위치를 누를 경우 A의 배수들만 조정이 되는 것이므로 그냥 A가 낮은 순서대로 그리디하게 확인하면 된다. 즉, 1번부터 차례대로 볼 경우 A번 스위치가 'Y'라면 A+1이상의 스위치에서는 A번 스위치를 끌 수 있는 경우 자체가 없으므로 무조건 A번은 눌러야 하는 것이다. 그렇다고 그 뒤의 스위치를 먼저 누른 후에 그 이전 스위치를 누른다고 더 횟수가 줄어드는 경우도 존재하지 않는다. 따라서 단순하게 1번부터 차례대로 확인하면서 'Y'라면 그 뒤의 스위치가 어찌됬든 무조건 꺼나가면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class.. 2022. 2. 16.
백준 1339 자바 - 단어 수학 (BOJ 1339 JAVA) 문제 : boj1339 1. 그리디 문제이다. 대충봐도 어떠한 문자를 9~0 중 어떤걸 선택해야 하는지 파악해야 하는 문제이므로 그리디 문제임을 알 수 있다. 이 때, 단순히 자리수가 높다고 높은 수를 줘버리면 다음과 같은 반례를 통과할 수 없다. A가 가장 자리수가 높으므로 9를 주고, Z를 8을 주면 총 합은 1780이 된다. 하지만 A를 8, Z를 9로 하면 1790이 나오므로 Z를 9로 주는 것이 이득임을 알 수 있다. 10 AZZ ZZ ZZ ZZ ZZ ZZ ZZ ZZ ZZ ZZ 2. 해결 방법 각 자리수에 대해 가중치를 주는 방식으로 해결할 수 있다. 즉, 1의 자리에 나온 문자는 가중치 1, 10의 자리는 10, ... 이런식이다. 예를들어 '예제 입력 2'는 다음과 같이 표현할 수 있다. [.. 2022. 2. 15.
백준 16208 자바 - 귀찮음 (BOJ 16208 JAVA) 문제 : boj16208 1. 우선 그냥 풀어보자. 결국 현재 막대 크기를 x+y로 나눌 수 있을 때, 비용인 xy들의 합을 최소로 하고 싶은 것이다. 그렇다면 수학적으로 최대한 '작은수 x 큰수'가 되도록 하는것이 최소이다. '중간수 x 중간수'일수록 손해이다. 예를들어 현재 길이가 10일 경우 5x5는 25지만 1x9는 9다. 또한 맨 마지막 막대는 비용이 0이므로 (x+0 이므로 xy = 0) 결국 주어진 n개의 쇠막대를 길이가 짧은 순서대로 나누면 된다(그리디 알고리즘). 내 경우엔 어차피 a_i 0) { int cur = Integer.parseInt(st.nextToken()); cnt[cur]++; sum += cur; } long answer = 0; for (int i = 1; i 0) .. 2022. 2. 7.
백준 20126 자바 - 교수님의 기말고사 (BOJ 20126 JAVA) 문제 : boj20126 각 시험이 서로 겹치지 않는다는 점 때문에 상당히 쉽게 풀 수 있다. 결국 모든 시험이 겹치지 않으므로, 각 시험의 비어있는 구간이 M 이상인지만 확인하면 된다. 즉, i번째 시험을 arr[i] 라고 한다면, arr[i].x - (arr[i-1].x + arr[i-1].y) 의 값이 M보다 크다면 문제의 조건을 만족하는 시간이 된다. 예를들어 다음의 입력을 봐보자. 3 4 20 3 1 7 5 13 3 위의 그림 중 첫번째 이미지처럼 다른 시험들이 진행될 것이다. 이 때 우리가 확인해야 할 부분은 두번째 이미지의 파란 부분이다. 정렬 후 위에서 제시한 공식대로 진행한다면 어렵지 않게 찾을 수 있다. 답은 16이 될 것이다. 그리고, 그림에서도 나오듯이 주의점은 0-3 구간과 16-.. 2022. 2. 1.
백준 1439 자바 - 뒤집기 (BOJ 1439 JAVA) 문제 : boj1439 아래 에미지에서 첫줄 '11'을 바꿈으로써 그 양옆 '00'들을 한꺼번에 바꿀 수 있는 것 처럼 중간에 있는 무언가를 바꾼다면, 그 다음 더 넓은 지역을 바꾸는데 도움이 된다고 생각할 수 있다. 그래서 어떻게 생각할 지 어렵게 여겨질 수 있다. 하지만 이러한 경우에 어떻게 하든 결국 중간중간 바꾼 것과, 모든 연속된 1 토큰을 0으로 바꾸거나 모든 연속된 0 토큰을 1로 바꾸는 것 중 작은쪽은 횟수가 똑같다. 무슨 말이냐면 그냥 아래와 같이 연속된 1로 구성된 토큰의 개수와, 연속된 0으로 구성된 토큰의 개수 중 작은쪽을 출력하면 끝나는 아주 간단한 문제라는 얘기이다. (만약 '11111' 이런식이었다면 0으로 된 토큰이 0일 것이므로 0이 답) 코드 : github import .. 2022. 1. 31.
백준 15922 자바 - 아우으 우아으이야!! (BOJ 15922 JAVA) 문제 : boj15922 결국 겹치는 구간은 무시하고, 모두 그려봤을 때 실제 포함되는 구간만을 구하면 된다. 이에 따라 예제 입력 1은 다음과 같이 생각해볼 수 있다. 그렇다고 배열같은거에 기입하자니 20억개나 표현이 가능해야하고, 당연히 이건 단순 순회만으로도 시간초과가 나게 된다. 따라서 내 경우엔 우선 각 x값을 기준으로 정렬한 후 현재 측정중인 구간의 시작 x와 끝점 y를 따로 기록해뒀다(코드에서 s와 e). 로직은 다음과 같다. A. x값을 기준으로 오름차순으로 정렬된 데이터를 차례대로 확인한다. 첫 s와 e는 즉 가장 x가 낮은 데이터 중 하나의 값과 동일해진다. B. 이후 각 (x,y)를 순회하면서 x가 e 이하라면 이전까지 보고 있던 (x,y)와 같은 구간으로 칠 수 있으므로 e만 조정한.. 2022. 1. 28.
백준 1817 자바 - 짐 챙기는 숌 (BOJ 1817 JAVA) 문제 : boj1817 '책은 탑처럼 차곡차곡 쌓여있기 때문에, 차례대로 박스에 넣을 수밖에 없다.' 부분이 없었다면 좀 더 어려웠을텐데, 이 문제의 경우 차례대로 넣을 수 밖에 없으므로 매번 최선의 선택만 진행하면 된다. (그리디 알고리즘) 입력을 받으면서 M의 무게를 다 채울 때 까지 계속 진행하고, M이상이 되었다면 무게를 다시 리셋하고 박스의 개수를 올리는 방식을 모든 입력값에 대해 취하면 해결할 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private void solution() throws Ex.. 2022. 1. 27.

티스토리툴바