멘지의 기록장

난이도🥈 3 링크https://www.acmicpc.net/problem/20115문제풀이과정해당 문제는 그리디를 사용하는 문제라고 되어 있지만, 사실 진짜 그리디를 사용하여 문제를 풀지는 않았다. 에너지 드링크의 양을 최대로 해야 된다고 했기에➡️ 가장 양이 많은 에너지 드링크의 양을 최대한 보존하기 위해 처음 값을 최댓값으로 설정하였다.➡️ 이후 나머지 값은 어떻게 정렬이 되어 있더라도 절반 값만 가져갈 수 있기 때문에 절반 값만 가져갈 수 있도록 코드를 작성하였다.  🚨 자바에서 나눗셈을 할 경우 몫만 가져가게 되기 때문에 나머지 값까지 가져가고 싶다면 double을 사용해야 한다!      나누는 값 중 하나라도 double 이라면 결과값이 double이 된다! 결과

난이도 🥈 1 링크 https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 문제 풀이과정 해당 문제는 DP를 사용하는 문제이다. DP를 사용하는 가장 기본적인 문제라고도 할 수 있는데 처음에는 문제가 잘 이해가 되지 않아서 다른 사람들의 풀이방법을 참고하였다. 예제 입력 1을 참고하여 설명해보자면 1) 우선 첫번째 곡은 시작 볼륨이 5이고 조절할 수 있는 볼륨이 5라면 ➡️ 첫번째 곡은 볼륨이 0이 되거나 10이 ..

난이도 🥇 5 링크 https://www.acmicpc.net/problem/14921 14921번: 용액 합성하기 홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데, 같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다. 당신 www.acmicpc.net 문제 풀이과정 해당 문제는 투 포인터를 사용하는 문제이다. 이분탐색과 비슷한 형식이기 때문에 풀이 형식이 익숙하다. 맨 앞과 맨 뒤에 각각 2개의 포인터를 두고서 하나씩 움직이며 원하는 값을 얻어내면 된다. 해당 문제에서는 두 용액을 합성하여 0에 가장 가까운 값을 만드는 것이 핵심이었기에 1) 투 포인터를 사용하여 우선 맨 앞과 맨 뒤의 2개의 용..

난이도 🥇 5 링크 https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의 www.acmicpc.net 문제 풀이과정 해당 문제는 그리디를 사용하는 문제이다. 예전에 풀었던 비슷한 문제에서는 종료 시점을 기준으로 정렬했기 때문에 이를 토대로 문제를 풀어보려고 했는데 잘 되지 않았다. 그래서 왜 안되지라고 생각하면서 반례를 찾아보니 안되는 반례를 찾았다! 만약 4개의 회의가 있고 각각의 시작 시간과 종료 시간이 다음과 같을 때 0 2 1 4 2 6 4 5 종료 시간을 기준으로 ..

난이도 🥈 1 링크 https://www.acmicpc.net/problem/3187 3187번: 양치기 꿍 입력의 첫 번째 줄에는 각각 영역의 세로와 가로의 길이를 나타내는 두 개의 정수 R, C (3 ≤ R, C ≤ 250)가 주어진다. 다음 각 R줄에는 C개의 문자가 주어지며 이들은 위에서 설명한 기호들이다. www.acmicpc.net 문제 풀이과정 해당 문제는 그래프의 전형적인 문제이다. BFS()를 사용해서 풀었고, 그래프의 문제들은 풀이 방법이 고정적이고 조금씩 바뀌기 때문에 백준을 시작할 때 가장 풀기 좋은 유형이 아닐까 싶다! 해당 문제도 그래프 문제의 전형적인 패턴을 따르면 되는 문제였다. 1) 입력받은 값들을 배열에 저장 2) 방문하지 않은 곳이면서 울타리가 아닌 부분에서 BFS() ..

난이도 🥇 4 링크 https://www.acmicpc.net/problem/1034 1034번: 램프 첫째 줄에 N과 M이 주어진다. N은 행의 개수이고, M은 열의 개수이다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져 www.acmicpc.net 문제 풀이과정 해당 문제는 부르트포스를 사용한다고 적혀있지만 그리디를 사용하는 문제이다. 그 이유는? 부르트포스를 사용하게 되면 행과 열이 50이하인데 모든 과정을 돌아보려면 2^열 인 2^50 가지의 경우의 수가 되어 시간초과가 뜬다.. 그래서 그리디를 사용해서 규칙을 찾는 것이 중요하다! 처음에 문제가 이해가 안돼서 한참 찾아보면서 문제를 이해해보았다. (근데 문제를..