본문 바로가기

그리디93

CodeForces 1614A - Divan and a Store (Java) 문제 : https://codeforces.com/contest/1614/problem/A 처음엔 냅색문제로 예상했는데, 생각해보니 그냥 작은 값부터 그리디로 확인해봐도 만족할 것 같아 노선을 변경함! 1. 우선 전처리로, 입력으로 들어온 a 중 l 미만이거나 r 초과인 값은 버려버린다. 2. '1'에서 걸러서 남겨진 값들을 정렬한다. 3. 이제 그리디하게 작은 숫자부터 k에서 빼가면서, 0보다 작아지는 경우 그 전까지 구매할 수 있다. 코드 : github import java.io.DataInputStream; import java.io.IOException; import java.util.ArrayList; import java.util.Collections; import java.util.Comp.. 2021. 11. 27.
백준 2697 자바 - 다음수 구하기 (BOJ 2697 JAVA) 문제 : https://www.acmicpc.net/problem/2697 A와 같은 구성에 A보다 큰 수 중 가장 작은 수는 그리디로 해결할 수 있다. 사실 이건 그리디야! 하고 푼건 아니고, 규칙을 찾고보니 그리디 스러운 규칙이었다.ㅋㅋ 1. 수를 뒤에서부터 한 자리씩 보면서, 처음으로 수가 이전보다 작아진 지점을 찾는다. 해당 지점을 T라고 하겠다. 2. T위치 이전은 그대로 출력한다. 그리고 T 위치를 포함해, 그 이후 위치에 대해 나왔던 숫자들을 몇번씩 나왔는지 카운팅한다. 3. T 이후의 위치에 있는 수 중, T에 해당하는 수보다 크면서 가장 작은 수를 찾아 T의 위치에 넣는다. 4. 카운팅해둔 값을 가지고, 작은 숫자부터 차례대로 카운팅값 횟수만큼 출력한다. 설명하기가 애매하니 예시를 들어 .. 2021. 11. 26.
백준 20310 자바 - 타노스 (BOJ 20310 JAVA) 문제 : https://www.acmicpc.net/problem/20310 사전순으로 가장 빠른 것이 되려면 결국 최대한 0이 앞쪽으로 와야하고, 최대한 1이 뒤쪽으로 가야한다. 그래서 생각보다 간단하게 풀 수 있는데, 단순히 1은 앞에서부터 지우고, 0은 뒤에서부터 지우면 된다. 다음과 같은 경우를 보자. 1은 4개이므로 2개를 지워야 한다. 0은 2개이므로 1개를 지워야 한다. 로직은 다음과 같다. 1. 편히 풀기위해 문자열을 character 배열 형태로 변경한다. 2. '1'이 들어있는 부분만 보면서, 지워야 하는 개수만큼 앞에서부터 순서대로 지운다. (따라서 이 풀이는 그리디!) 3. '0'이 들어있는 부분만 보면서, 지워야 하는 개수만큼 뒤에서부터 순서대로지운다. --- 코드 : https:.. 2021. 11. 14.
백준 2405 자바 - 세 수, 두 M (BOJ 2405 JAVA) 문제 : https://www.acmicpc.net/problem/2405 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02400/BOJ_2405.java 1. a 2021. 11. 12.
백준 2437 자바 - 저울 (BOJ 2437 JAVA) 문제 : https://www.acmicpc.net/problem/2437 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02400/BOJ_2437.java 일단 brute force(완전탐색)으로는 단순히 생각해봐도 2^1000 이므로 절대 무리다. 처음엔 DP류 일 것 같았는데, 결론적으로 완전 아이디어 하나로 풀리는 문제였다. 내 경우엔 공책에 막 여러 케이스 무지성으로 써보면서 확인해보다가 얻어걸렸다. 일단 '양의 정수 무게 중 최솟값' 이라는 부분에서, 최소값을 찾자마자 출력해야 할꺼라 판단하여 정렬부터 하고 생각했다. 그리고 잘 보면 애초에 '2 3 4 5 6' 이렇게 있어도 1이 없으면 1은 못만든다. 그다음으로 '1 .. 2021. 11. 12.
백준 1036 자바 - 36진수 (BOJ 1036 JAVA) [ 백준 1036 - 36진수 ] [ 코드 보기 (깃헙 링크) ] 23046(큰 수 뒤집기)를 얼마전에 푼 이후로 당분간 큰 수 연산 관련된건 안보려 했으나, 그냥 그리디에 36진수 자리수 올림 (carry) 정도만 필요한것같아 시도했다가 로직 자체가 틀리면서 물렸다.. 그 뒤로 맞는 것 같은 로직을 세웠는데, 결국 더 많은 큰 수 연산이 필요했다 ㅠㅠ 그래도 이번엔 BigInteger로도 입력 숫자 자체가 적다보니 문제없어서 다행이었다.. 로직 자체는 그리디인데, 로직보다도 구현 자체가 빡쌨던 문제이다. [ 틀린 로직 ] 가끔씩 틀린 로직도 적는데, 누구 보라고 적는건 아니고 나중에 내가 다시 봤을 때 이렇게 틀렸었지! 하기 위해서이다. 그러니 아래쪽의 'AC 코드 해설'로 바로 넘어가도 상관없음. 처.. 2021. 11. 7.
백준 2786 자바 - 상근이의 레스토랑 (BOJ 2786 JAVA) [ 백준 2786 - 상근이의 레스토랑 ] [ 코드 보기 (깃헙 링크) ] 쉬운 것 같으면서도 은근 생각할게 좀 있었다. 일단 생각 과정을 적어본다. 1. 첫 음식이 A가격이 아니고 B가격만 있었다면 어떻게 계산할까? -> 음식을 입력받은 순서와 관계없이 B가격만 영향을 끼치므로, 그리디하게 B 가격 순서대로 구매한다고 생각하면 된다. 따라서 B를 기준으로 정렬한 후 prefix sum(누적 합) 배열 하나 만들어두면 쉽게 출력 가능하다. 결국 첫 음식은 A가격을 지불해야 하는 부분만 잘 처리하면 되는 문제이다. 2. 음식을 1개 시킬 때 최소 가격 : [전체 중 최소 A 값] 3. 음식을 n개(전부) 시킬 때 최소 가격 : [모든 B를 더한 값] + [(A-B)의 최소값] -> 2,3번을 합쳐서 그럼 .. 2021. 11. 6.
백준 1138 자바 - 한 줄로 서기 (BOJ 1138 JAVA) [ 문제보기 ] [ 코드보기(깃헙) ] N이 최대 10이다. 따라서 모든 경우를 보려면 10! 번을 봐야한다. 이 경우 362880번으로, 사실 모든 경우를 봐도 가능하긴 하다! 다해봐야 O(N! * N) 정도이다. 사실 시간복잡도, 메모리복잡도 면에서 모두 이득인 방법이 더 있다. 어차피 입력이 키가 1인 사람부터 차례대로 들어오기 때문에, 키가 큰 사람부터 순서대로 입력을 만족하는 위치에 넣어버리면 된다. (따라서 그리디 알고리즘 분류다.) 4 2 1 1 0 의 입력을 확인해보자. 이 경우 키가 1인 사람은 좌측에 2명, 2인 사람은 좌측에 1명, 3인 사람은 좌측에 1명, 4인 사람은 좌측에 아무도 없다는 입력이다. 키가 작은 사람부터 보자면 어려운 문제가 확실하지만, 키가 큰 사람부터 보면 엄청 .. 2021. 11. 3.
자바 6137 자바 - 문자열 생성 (BOJ 6137 JAVA) 문제 : https://www.acmicpc.net/problem/6137 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/06100/BOJ_6137.java 문제에 제시된 '예제 입력 1'을 기준으로 그림을 그려보면 다음과 같다. 위와 같이 문자열이 있고, head가 앞쪽 tail이 뒤쪽을 가르키는 포인터라 생각하면 된다. 그리고 head는 우측으로, tail은 좌측으로 진행하면서 사전순으로 더 작은 character를 선택하면 된다. (A 2021. 10. 29.
백준 21941 자바 - 문자열 제거 (틀린 풀이 - 새로 작성한 풀이 링크 포함) -- 이하 틀린 풀이이다. -- 새로 작성한 풀이 : 링크 문제 : https://www.acmicpc.net/problem/21941 풀고보니 DP로만 분류되있어서(알고리즘 분류 켜놓으면 너무 치트라 꺼놨음) 약간 의아했다. 내 경우엔 그리디로 풀었다. 물론 DP를 더 간단하게 생각하는 분들이 많겠지 ㅠ 1. 일단 a의 길이가 x보다 크거나 같다면 버린다. 예제 입력2의 경우를 처리하기 위해서이다. 2. 그다음 가장 점수를 많이 주는 녀석부터 하나씩 빼낼껀데, 단순히 'x'만 판단하면 안된다. 왜냐면 다음과 같은 경우가 있을 수 있다. abcdefg 10 a 9 둘 다 '1'에서 걸러지지 않지만, 누가봐도 'a 9'를 쓰는게 이득임을 알 수 있다. 따라서 [ x / a의길이 ] 가 높은 순서대로 먼저 .. 2021. 10. 23.

티스토리툴바