greedy

[백준, Java] 1052번 : 물병

🔗 문제 링크 https://www.acmicpc.net/problem/1052 😮 문제 해결 방법 문제에서 같은 양이 들어있는 물병끼리 하나로 합칠 수 있고 처음에는 모든 물병에는 물이 1L가 들어있다고 제시되어 있다. 처음부터 두 개의 물병을 한 개의 병으로 합쳐가면, 2L → 4L → 8L 이런식으로 증가할 수 밖에 없다. 이는 물병이 2의 제곱 값이 되어야 병이 하나로 합쳐지는 것을 알 수 있다. N개의 물병을 K개의 물병으로 합치는 경우 최소 개수의 물병을 사기 위해선 남은 물병(N) 보다 작으면서 가장 큰 2의 제곱 값을 매번 구해 빼주는 작업을 K-1번 해주고, 그래도 물병이 남아있다면 마지막(K번째)에는 남은 물병으로 한 병을 만들어야 하므로 남은 물병보다 크면서 가장 작은 2의 제곱값을 ..

[ 백준, Java] 1339번 : 단어 수학

🔗 문제 링크 https://www.acmicpc.net/problem/1339 🤔 문제 민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다. 단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다. 예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다. N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그..

[백준, Java] 16120번 : PPAP

🔗 문제 링크 https://www.acmicpc.net/problem/16120 😮 문제 해결 방법 스택을 이용해서 문제를 해결했다. ‘P’가 들어오는 경우 스택에 저장하고, ‘A’가 들어오는 경우는 PPAP 문자열인지 판단해주었다. ‘A’가 들어오는 경우 PPAP 문자열인지 판단하기 위해 바로 다음 인덱스 문자가 ‘P’인지 판단하고 스택 사이즈가 2 이상 (스택에는 ‘P’만 들어감)인지 확인 후 스택을 두번 pop해 주었다. 결론적으로, 스택에서 pop된 문자 2개 PP와 현재 인덱스 A, 다음 인덱스 P가 되어 문자열 PPAP가 만들어지므로 다음 인덱스 ‘P’로 대체가 가능하다. 이외의 경우는 PPAP문자열을 P로 대체할 수 없으므로 “NP”를 리턴한다. 모든 PPAP 문자열이 P로 대체된다면, 마..