백준17 [백준] 1495 : 기타리스트 (JAVA) 난이도 🥈 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이 .. 2024. 1. 22. [백준] 14921 : 용액 합성하기 (JAVA) 난이도 🥇 5 링크 https://www.acmicpc.net/problem/14921 14921번: 용액 합성하기 홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데, 같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다. 당신 www.acmicpc.net 문제 풀이과정 해당 문제는 투 포인터를 사용하는 문제이다. 이분탐색과 비슷한 형식이기 때문에 풀이 형식이 익숙하다. 맨 앞과 맨 뒤에 각각 2개의 포인터를 두고서 하나씩 움직이며 원하는 값을 얻어내면 된다. 해당 문제에서는 두 용액을 합성하여 0에 가장 가까운 값을 만드는 것이 핵심이었기에 1) 투 포인터를 사용하여 우선 맨 앞과 맨 뒤의 2개의 용.. 2024. 1. 21. [백준] 19598 : 최소 회의실 개수 (JAVA) 난이도 🥇 5 링크 https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의 www.acmicpc.net 문제 풀이과정 해당 문제는 그리디를 사용하는 문제이다. 예전에 풀었던 비슷한 문제에서는 종료 시점을 기준으로 정렬했기 때문에 이를 토대로 문제를 풀어보려고 했는데 잘 되지 않았다. 그래서 왜 안되지라고 생각하면서 반례를 찾아보니 안되는 반례를 찾았다! 만약 4개의 회의가 있고 각각의 시작 시간과 종료 시간이 다음과 같을 때 0 2 1 4 2 6 4 5 종료 시간을 기준으로 .. 2024. 1. 20. [백준] 3187 : 양치기 꿍 (JAVA) 난이도 🥈 1 링크 https://www.acmicpc.net/problem/3187 3187번: 양치기 꿍 입력의 첫 번째 줄에는 각각 영역의 세로와 가로의 길이를 나타내는 두 개의 정수 R, C (3 ≤ R, C ≤ 250)가 주어진다. 다음 각 R줄에는 C개의 문자가 주어지며 이들은 위에서 설명한 기호들이다. www.acmicpc.net 문제 풀이과정 해당 문제는 그래프의 전형적인 문제이다. BFS()를 사용해서 풀었고, 그래프의 문제들은 풀이 방법이 고정적이고 조금씩 바뀌기 때문에 백준을 시작할 때 가장 풀기 좋은 유형이 아닐까 싶다! 해당 문제도 그래프 문제의 전형적인 패턴을 따르면 되는 문제였다. 1) 입력받은 값들을 배열에 저장 2) 방문하지 않은 곳이면서 울타리가 아닌 부분에서 BFS() .. 2024. 1. 17. [백준] 1034 : 램프 (JAVA) 난이도 🥇 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 가지의 경우의 수가 되어 시간초과가 뜬다.. 그래서 그리디를 사용해서 규칙을 찾는 것이 중요하다! 처음에 문제가 이해가 안돼서 한참 찾아보면서 문제를 이해해보았다. (근데 문제를.. 2024. 1. 15. [백준] 13975 : 파일 합치기 3 (JAVA) 난이도 🥇 4 링크 https://www.acmicpc.net/problem/13975 13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net 문제 풀이과정 해당 문제는 그리디를 사용하는 문제이다. 생각해보면 굉장히 쉽게 풀 수 있는 문제여서 문제 설명에 쓰여진 예시를 보지 않는게 더 도움이 될 거 같다.. 예시 설명에서는 [40 30 30 50] 이라는 값이 있을 때 1) 먼저 40 + 30 = 70 2) 30 + 50 = 80 3) 70 + 80 = 150 이러한 과정으로 결과값을 출력하도록 설명하였는데 이렇게.. 2024. 1. 14. 이전 1 2 3 다음
