두부의 코딩일기

https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net ✅ 골드 Ⅱ 🔶 풀이 보드에 적힌 숫자만큼 동,서,남,북 4방향으로 이동하면서 최대 몇 번의 동전을 움직일 수 있는지 구하는 문제. dfs와 dp를 이용하는 문제. 1️⃣ 동전이 구멍에 빠지거나 보드의 바깥으로 나가면 게임 종료 2️⃣ 동전을 무한번 움직일 수 있을 경우 -1을 출력 게임이 종료되는 조건은 위와 같다. 1️⃣번 조건은 dfs, bfs를 한 번이라도 풀어봤다면 쉽게 해결할 수 있다...

https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net ✅ 골드 Ⅴ 🔶 풀이 N가지 종류의 동전이 주어지면 동전을 최대한 적게 사용해서 K원을 만들어라. 다이나믹 프로그래밍(dp) 문제로 아래의 조건만 신경써주면 딱히 어려운 게 없는 문제라고 생각한다. 1️⃣ 각각의 동전을 여러 개 사용할 수 있음 2️⃣ 정확하게 K원을 만들지 못 하면 -1을 출력함 예제로 점화식을 찾아보겠다. 1원 동전 1 2 3 4 5 6 7 8 ..

https://www.acmicpc.net/problem/2073 2073번: 수도배관공사 아기염소들이 언덕에서 풀을 뜯고 놀다 보면 항상 도중에 목이 마르곤 했다. 그들은 불편함을 참지 못하고 수도관을 설치하여 거리 D(7 ≤ D ≤ 100,000)만큼 떨어진 곳의 강에서 물을 끌어오기로 www.acmicpc.net ✅ 골드 Ⅳ 🔶 풀이 해당 문제는 다이나믹 프로그래밍(dp)로 문제의 조건은 아래와 같다. 1️⃣ 파이프는 하나씩 사용이 가능하고, 수도배관 길이는 강까지의 거리(D)와 동일해야 한다. 2️⃣ 수도배관을 완성했을 경우, 가장 적은 용량을 가진 파이프가 해당 수도배관의 용량이다. 3️⃣ 동일한 길이를 가진 여러 개의 수도배관 중에 가장 큰 용량을 구하라. 파이프의 길이를 정확하게 강까지의 거..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net ✅ 실버 Ⅰ 🔶 풀이 N개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓값을 구하시오. 다이나믹 프로그래밍 문제다. 예제 2번으로 규칙을 찾아보겠다. 카드팩은 총 5개이고, 카드 5개를 구매하기 위해 지불해야 하는 최대 금액을 찾으면 된다. P1 = 10, P2 = 9, P3 = 8, P4 = 7, P5 = 6 card[1] = 10, card[2] = 9, card[3] = 8, card[4] = ..

https://www.acmicpc.net/problem/1563 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net ✅ 골드 Ⅳ 🔶 풀이 dp[날짜][지각 횟수][연속으로 결석한 횟수] 를 기준으로 dp 배열을 생성했다. 개근상을 받을 수 있는 조건은 총 6가지다. 1. 0번 지각, 0번 연속 결석 → dp[N][0][0] 2. 0번 지각, 1번 연속 결석 → dp[N][0][1] 3. 0번 지각, 2번 연속 결석 → dp[N][0][2] 4. 1번 지각, 0번 연속 결석 → dp[N][1][0] 5. 1번 지각, 1번 연..

https://www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1 ≤ W ≤ 1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄 www.acmicpc.net ✅ 플레티넘 Ⅴ 🔶 풀이 경찰차 A (1, 1) 과 경찰차 B (N, N) 이 있다. 순서대로 사건이 일어났을 때, 경찰차가 이동하는 최소 거리의 합을 구하라. 해당 문제도 dp다. 하지만 점화식을 찾는 dp는 아니고, dfs를 이용해서 문제를 해결해나가면 된다. dp[one][two] 는 "경찰차 A의 위치가 one번째 사건이고, 경찰차 B의 위치는 two번째 사건에 위치..

https://www.acmicpc.net/problem/11570 11570번: 환상의 듀엣 상덕이와 희원이는 소문난 환상의 듀엣으로, 노래방에 가서 노래를 자주 부르곤 한다. 어느 날 상덕이는 백준이에게 선물 받은 악보를 가져왔다. 악보에는 그 노래를 표현하는데 필요한 음의 높 www.acmicpc.net ✅ 플래티넘 Ⅴ 🔶 풀이 내가 선택한 플래티넘 문제는 개인적으로 가장 어려워하는 dp.. 음의 차이를 나타내는 힘든 정도의 최솟값을 구하라. 문제의 이해를 돕기 위해 편의상 상덕이를 A, 희원이를 B로 하겠다. dp 배열은 각자 마지막으로 부른 음을 기준으로 힘든 정도의 최솟값을 저장해줬다. 현재 상태: dp[A가 마지막으로 부른 음][B가 마지막으로 부른 음]; A가 다음으로 부를 경우: dp[n..

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 🔶 풀이 불특정한 도시 A에서 출발해서 한 바퀴를 돌고 도시 A로 다시 돌아왔을 때 최소 비용을 구하는 문제. 시간 제한이 적기 때문에 dp와 비트마스크를 활용해야함. 비트마스크(Bit Mask) 알고리즘 장점 및 연산자 사용 방법 비트마스크(BitMask)는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여 정수의 이진수 표현을 자료 구조로 쓰는 기법 ✅ 이진..

https://www.acmicpc.net/problem/1102 1102번: 발전소 첫째 줄에 발전소의 개수 N이 주어진다. N은 16보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 발전소 i를 이용해서 발전소 j를 재시작할 때 드는 비용이 주어진다. i줄의 j번째 값이 그 www.acmicpc.net 🔶 풀이 비트마스킹 dp. 이 문제를 해결하기 위해서 비트마스크를 공부했다. 공부 내용은 추후에 올릴 예정✌️ 2023.04.17 추가 - 비트마스크 참고 포스팅 비트마스크에서 흔히 사용하는 연산은 두 가지다. 1. num | (1

https://www.acmicpc.net/problem/1028 1028번: 다이아몬드 광산 첫째 줄에 R과 C가 주어진다. R과 C는 750보다 작거나 같은 자연수이다. 둘째 줄부터 R개의 줄에는 다이아몬드 광산의 모양이 주어진다. www.acmicpc.net 🔶 풀이 처음으로 도전한 플레티넘 문제, 퇴근 후에 하루종일 풀었다... 최근에 풀었던 [가장 큰 정사각형] 문제 상위버전인듯하다. row와 col의 최대 크기는 750, 단순 완전 탐색으로는 시간초과가 발생하기 때문에 dp를 활용해야 함 1. map[row][col]에서 값이 1인 경우에 4방향(↙ ↘ ↖ ↗)으로 뻗어나가면서 변의 길이를 구한다. public static int getSize(int x, int y, int d) { int ..