본문 바로가기

Greedy79

백준 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.
백준 2759 자바 - 팬케이크 뒤집기 (BOJ 2759 JAVA) https://www.acmicpc.net/problem/2759 알고리즘 분류를 굳이 따지자면 constructive, ad-hoc, greedy 쪽일 것 같음. 애초에 답으로 가능한 경우 어떤 것이든 출력하면 되기도 하고, 이런 류의 문제를 풀기위한 well-known 스러운 풀이도 없다고 판단되므로 논리적 추론을 통해 이 문제만의 풀이과정을 만들어야 하는 종류의 문제이다. Brute force로 모든 경우를 보면 최대 O(30^30) 이라는 괴랄한 수가 나오므로 절대 무리.. 전 일단 가장 큰 수 부터 차례대로 맨 아래로 가야한다는 부분에 포인트를 맞추고, 그럼 위에서 k개를 뒤집는 방식으로 어떻게 가장 큰 수부터 차례대로 맨 아래로 내릴지 생각해봤다. 결론적으로 제 풀이는 다음과 같음. 가장 큰 .. 2021. 10. 7.
백준 12931 자바 - 두 배 더하기 (BOJ 12931 JAVA) https://www.acmicpc.net/problem/12931 우선 처음으로 생각할 부분이, 만약 시작지점인 0,0,0,... 에서 시작해서 제시된 B 배열을 찾아가려면 결국 모든 경우를 봐야한다. 매번 B 배열과 비교하며 최소 연산 횟수를 찾게 짜는건 사실상 무리라고 본다. 그럼 반대로 B 배열에서 0,0,0,...을 찾아가는걸 생각해보자. 제시된 연산은 각각에대해 1을 더하는 것과 전체에 대해 2를 곱하는 것이므로, 반대로 B배열에서 0,0,0,... 을 찾아가기 위해서는 각 배열에 대해 1을 빼는 연산과, 전체에 대해 2로 나누는 과정을 거쳐야 한다. 그럼 N=1일 때 조차도 무조건 2로 나누는 것이 이득인 것을 쉽게 알 수 있다. (더 적은 연산으로 차이를 더 많이 낼 수 있음) 최종적으로 .. 2021. 10. 5.

티스토리툴바