본문 바로가기

그리디94

백준 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.
백준 1294 자바 - 문자열 장식 (BOJ 1294 JAVA) 문제 : https://www.acmicpc.net/problem/1294 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01200/BOJ_1294.java 쉬운줄 알고 덤볐는데 생각보다 어려웠지만, 결국 다 풀고보니 또 그렇게 어렵진 않았던 문제. 1. 기본 로직은 어렵지 않게 생각해볼 수 있다. 3 ABC BCD CDE 만약 입력이 위와 같다고 하자. 각 문자열의 순서를 해치지 않으면서 전체 문자열이 사전순으로 앞서게 하려면 결국 각 문자열에 pointer를 뒀다고 생각하고, 해당 문자열의 pointer가 가르키는 문자 중 가장 작은걸 순서대로 빼내면 된다. 즉, 위의 경우 다음과 같이 진행된다. 1.1 시작은 아래와 같다. 화.. 2021. 10. 23.
백준 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.

티스토리툴바