그리디93 백준 1806 자바 - 부분합 (BOJ 1806 JAVA) 문제 : boj1806 1. 틀린 방법 ※ 제가 틀린 방법에 대해 써둔 것으로, 해설만 보고 싶다면 2번부터 보시면 됩니다. 덱에 모든 값들을 담으면서 그 합을 따로 계산한다. 그럼 일단 그 합은 최대치로 나올 수 있는 합이 될 것이다. 그 합이 S보다 작다면 0을 출력하고, 그렇지 않다면 합이 S보다 작아질 때 까지 덱의 시작부분과 끝부분을 각각 peek 해봐서 둘 중 작은 값을 덱에서 빼버린다. 이렇게 하면 그리디하게 답을 구할수 있을줄 알았다. 예를들어 S가 5일 때 다음과 같이 수행한다. 이렇게 짠 코드는 다음과 같다. ※ 틀린 코드임 ... int n = nextInt(); int s = nextInt(); int sum = 0; Deque dq = new ArrayDeque(); for (in.. 2022. 1. 23. 백준 2012 자바 - 등수 매기기 (BOJ 2012 JAVA) 문제 : boj2012 1. 흔히 생각해볼만한게, 예를들어 '1 8 4 5 6'과 같은 입력이 있는 경우 총 1~5등 까지를 매칭시켜야 한다. 그렇다면 1~5등 사이 중 일단 자기가 원한 등수가 가능한 녀석들을 매칭시키자. 그럼 1, 4, 5는 1~5등 내에 매칭이 가능할 것이다. 이제 8과 6이 남는데, 당연하게도 정렬해서 매칭시키는 것이 더 정답에 가까울 것임을 유추할 수 있다. 따라서 정렬 후 차례대로 남는 위치에 매칭시키면 답을 구할 수 있다. '1'의 방법을 정리하면 1.1 N을 입력받는다. 1.2 1~N에 바로 매칭이 가능한 예상등수를 매칭시킨다. 1.3 남는 등수를 정렬한 후, 1~N 사이 남는 등수에 매칭시킨다. 이 된다. 2. 그런데 사실 더 쉬운 방법이 있다. 어차피 (|A-B|)의 합.. 2021. 12. 27. 백준 1132 자바 - 합 (BOJ 1132 JAVA) 문제 : boj1132 1. 쉽게 생각할 수 있는 방식인 단순히 자리수가 높다고 높은 수를 주는 방식은 쉽게 반례를 찾을 수 있다. AB B B B B B B B B B B 와 같은 입력에 대해 단순히 A가 자리수가 크다고 9를 주면 안된다. B가 11개인 위와 같은 경우 B를 9를 줘야 최대값이 나온다. 2. 이런 경우 자리수에 따른 가중치를 계산해야 한다. 1위 자리에 나온 수라면 +1의 가중치, 10의 자리라면 +10, ... 와 같은 방식이다. 예를들어 '예제 입력 1'에 나온 각 문자는 다음과 같이 가중치를 구할 수 있다. 그럼 가중치가 높은 순서대로 더 높은 수를 주면 된다(그리디). 따라서 B=9, A=8, C=7이 된다. 3. 만약 A~J가 아니라, A~I 까지 였다면 9~1을 주면 되니까.. 2021. 12. 18. 백준 3011 자바 - 이름 지어주기 (BOJ 3011 JAVA) 문제 : boj3011 1. A에서 B 구간의 최대가 10^9이므로, 우선 모든 경우를 봐서는 통과할 수 없음을 알 수 있다. 그럼 뭔가 정답 구간을 정할 수 있는 방법이 있다는 얘기이다. 이 문제의 경우, 어떠한 X 지점에 대해 모든 N지점 중 거리의 차가 최소인 지점을 최대한 멀리 두려고 한다(min{|X-Pi|, i ∈ [1,N]}). 즉, X는 모든 N개의 지점 P_i와 최대한 멀리 떨어지면 된다. 2. 입력이 4 10 46 56 70 10 70 인 경우를 생각해보자. 어떻게 해야 N개의 지점에서 가장 멀리 떨어진 X 지점을 모두 보지 않고 찾을 수 있을까? 최선의 선택은 각 지점들의 중간지점들을 보면, 그 중 가장 양쪽의 차이가 큰 지점을 고르면 될 것임을 생각해볼 수 있다(그리디). 그리고 하.. 2021. 12. 17. 백준 1011 자바 - Fly me to the Alpha Centauri (BOJ 1011 JAVA) 문제 : boj1011 다른 사람 코드들을 보니 규칙을 찾아 수식으로 해결한 경우가 많은 것 같다. 내 경우엔 그리디로 해결했다. x에서 y로 가면서 '최소값'을 구해야 한다. 이 경우, 최선의 선택은 x에서 1로 시작해 무조건 +1로만 진행하는 것이다. 점점 가속해야 가장 최선의 선택임이 자명하다. 하지만 문제는 y에서 도착할 때도 1이어야 한다. 그렇다면 최선의 선택은 다음과 같다. x에서 계속 +1씩 증가하면서 진행하고, y까지도 계속 -1씩 감소시키면서 감속시키는 것이다. 그럼 반대로 바꿔서 저 '?' 부분을 향해 x와 y에서 동일한 속도로 진행해서 만난다고 생각해보자. 그럼 x쪽에서1, y쪽에서1 -> x쪽에서2, y쪽에서2 -> x쪽에서3, y쪽에서3 이동.. 이런식으로 보면 되겠다. 이 때 .. 2021. 12. 8. 백준 2839 자바 - 설탕 배달 (BOJ 2839 JAVA) 문제 : boj2839 가장 작은 수의 봉지를 사용해야하므로 '5'를 최대한 많이 쓸수록 이득이다. 그리고 '정확히' n킬로그램을 선택해야한다. 따라서 최상의 선택인 '5'짜리 봉지를 'n/5'개 사용하는 것부터 시작해서 '5'짜리 봉지를 0개 까지 확인해보면서, 남은 설탕이 '3'짜리 봉지로 정확히 나눌 수 있다면 해당 지점이 최선의 선택이다. (그리디) 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamRea.. 2021. 12. 6. 백준 9081 자바 - 단어 맞추기 (BOJ 9081 JAVA) 문제 : boj9081 이하 설명은 이해의 편의를 위해 숫자로 설명해보겠다. 실제로 이 문제를 풀때도 문자를 아스키코드를 기준으로 변경해서('A'~'Z'까지 나오므로 각각을 숫자 0~25로 대입) 풀어야 한다. 내 풀이는 그리디 이다. 1. 문자를 뒤에서부터 보면서, 같거나 증가하는 경우는 계속 진행하고 처음으로 더 작아진 경우를 찾는다. (문자로 따지면 ADCB라면 D->A일 때 작아진다.) 이하 그림에서는 9->3이 처음으로 작아진 부분이다. 처음으로 숫자가 감소하는 부분에 나왔던 '3'에 해당하는 위치를 T라고 적겠다. 2. T위치와, 그 이후에 나온 숫자를 몇 번씩 나왔는지 카운팅한다. 이하 그림에서 idx 부분이 실제 숫자에 대입된다(문자라면 'A'~'Z'까지 카운팅하면 된다.) 예를들어 idx.. 2021. 12. 5. 백준 12966 자바 - 턴 게임 2 (BOJ 12966 JAVA) 문제 : boj 12966 수학적인 문제는 좀 피했었는데 오랜만에 도전한건데 잘 풀어낸 것 같아 기쁨. 사실 문제만 보고는 감이 잘 안왔었는데, 일단 주어진 부분에 대해 생각나는 것 부터 차례대로 쳐내다보니 답을 구할 방법이 보였다. 1. 일단 n번째(문제에서 'i'로 설명한걸 글에서는 'n'으로 표현한다. 'i'로 글쓰면 1이랑 헷갈린다.) 턴에 승리한 사람이 얻는 점수는 2n-1이다. 만약 n = 5라고 한다면 아래와 같이 된다. 즉, 점수는 모든 홀수인 셈이다. 2. 우선 불가능한 경우부터 예외처리를 해보자. 문제에서 제시된 게임은 1번째부터 순서대로 계속 진행을 해야 하고, 중간에 둘 다 점수를 못얻는 경우가 없다. 따라서 x와 y를 더한 값이 홀수의 등차수열 합과 일치해야 가능한 경우이다. 뭔소.. 2021. 11. 29. 백준 20856 자바 - Tunnelbaneplatser (BOJ 20856 JAVA) 문제 : boj 20856 입력받은 a1, a2, a3, a4에 대해 확실한것부터 제거해나가면서 선택해가면 된다(그리디). 이하 설명에서 cnt는 결과값으로 출력할 변수이다. 1. a4값만큼 cnt에 더한다. (4명이니 그냥 바로 앉으면 된다. 다른 그룹과 같이 앉을 수 없다.) 2. 다음으로 a2값을 보자. a2는 a2혼자 혹은 a2+a2, a2+2*a1의 형태로 가능하다. a3와 앉을 방법이 아예 없다. 따라서 a2를 2로 나눈 몫만큼 cnt를 더하고, a2를 2로 나눈 나머지가 있다면 cnt를 하나 더 올려주면 된다. 이 때 a1이 2 이상이라면 a1 두 그룹과 같이 앉고, 아니면 a2 혼자 앉으면 된다. 근데 사실 어차피 a2랑 같이 앉을 수 있는건 a1 뿐이므로 a1이 음수가 되던말던 상관없이 .. 2021. 11. 28. CodeForces 1614B - Divan and a New Project (Java) 문제 : https://codeforces.com/contest/1614/problem/B 어려워 보일 수 있는데, 더 많이 방문할수록 가까이 두면 된다. 예를들어 다음의 경우를 보자. 5 3 8 10 6 1 그럼 얘네들을 더 많이 방문하는 순서대로 정렬해보면 10 > 8 > 6 > 3 > 1이 된다. 그리고 시작지점을 '0'에 둔다고 해보자. 그럼 다음과 같이 배치하면 전체 거리가 최소가 된다. 즉 로직은 다음과 같다. 1. 들어온 값에 대해 내림차순으로 정렬한다. 이 때, 처음 들어왔던 순서를 알아야 정렬하더라도 처음 들어온 순서에 맞게 출력해줄 수 있다. 2. 시작점을 0으로 잡고, '1'에서 정렬한 순서대로 거리가 짧은곳에 둔다. (+1 -> -1 -> +2 -> -2 -> +3 -> ...) 시.. 2021. 11. 27. 이전 1 ··· 5 6 7 8 9 10 다음
