코딩테스트/BAEKJOON (4) 썸네일형 리스트형 백준: 1106. 호텔 (C++) 1. 문제 정보https://www.acmicpc.net/problem/1106Gold IV다이나믹 프로그래밍 2. 문제 풀이 전형적인 배낭 문제 유형이에요 !하지만 이번 문제를 풀면서 풀이 과정을 개선한 점, 그리고 새롭게 배운 점이 있어 정리해볼까 해요 🥰 2차원 배열 풀이원래 저는 배낭 문제를 풀 때 2차원 배열 형태로 풀어왔었어요첫 번째 예시를 예로 들어봅시다먼저 DP 배열은 DP[1001][100001]로 작성해줬어요N이 1000보다 작거나 같고, 각 도시에서 낼 수 있는 비용이 최대 100이므로C = 1000일 때 필요한 최대 비용은 100 * 1000이 됩니다이에 맞춰 예제 입력 1번에 대한 풀이를 해볼게요초기에는 이와 같은 2차원 배열로 시작합니다1번 도시의 경우, 3의 홍보 비용으로 .. 백준: 15708. 미네크래프트 (C++) 1. 문제 정보https://www.acmicpc.net/problem/15708Platinum V그리디 2. 문제 풀이 이번 문제도 역시 쉽진 않았어요처음에 풀이가 생각이 나지 않아 아래 쪽의 알고리즘 분류를 확인하고 감을 잡아 풀었습니다 🥲우선순위 큐를 활용한 문제였어요 T = 20, P = 1이라는 조건으로 위의 예시를 볼게요한 칸 한 칸 옆으로 이동해주며 사용 가능한 총 시간을 계산합니다위의 예시의 경우 p가 1이므로 한 칸 이동할 때 마다 1씩 감소하게 되겠지요 😀최대 힙을 이용해 우선순위 큐를 구성하고 미네랄의 위치에서 사용 가능 시간과 미네랄을 비교해 추가가 가능하면 큐에 넣어줍니다큐의 TOP과 미네랄을 비교했을 때, TOP이 현재 미네랄보다 크다면 제거해줍니다차례대로 한 번 살펴볼게요.. 백준: 17420. 깊콘이 넘쳐흘러 (C++) 1. 문제 정보https://www.acmicpc.net/problem/17420Platinum V그리디 2. 문제 풀이 처음 문제 풀이 시 부터 풀이가 쉽게 보이는 편이라고 생각하고 막힘 없이 풀기 시작했었어요하지만 그렇게 호락호락할 리가 없죠 🥲제대로 처리하지 못한 코너 케이스들에서 막히게 되었어요 😭그래서 ! 우리는 해당 케이스 분석으로 먼저 들어가보려 합니다 439 8 10 040 60 60 90AC: 10 이 케이스를 먼저 확인해 볼 건데요 이 문제 풀이의 핵심은 정렬에 있습니다문제의 조건을 보면 아래와 같습니다 기프티콘의 연장 횟수 최소화기프티콘의 기한이 가장 짧은 것 먼저 사용기프티콘의 사용 날짜는 정해져 있음기프티콘은 하루에 동시에 여러 장 연장 또는 사용할 수 있음이를 봤을 때, 기.. 백준: 1109. 섬 (C++) 1. 문제 정보https://www.acmicpc.net/problem/1109Platinum IV그래프 2. 문제 풀이 문제를 처음 봤을 때, 트리의 높이 문제라고 생각은 했으나 어떻게 트리를 구현해야 할 지 감이 잘 오지 않았어요 🥲 트리로 구현하려고 할 때 처음부터 한 번에 트리로 구현하려고 하니 많이 막혔던 것 같아요트리로 구현하지 않아도 풀 수 있는 방법도 있었구요 ! (지인이 이렇게 풀었더라구요 👀) 각각의 풀이 방법을 설명드릴게요 트리 구현 풀이법 (BFS 3회, DFS 1회)트리를 직접 구현해서 푸는 방식입니다# https://www.acmicpc.net/board/view/8509913 17xxxxxxxxxxxxxxxxxx...............xx.xxx.x...xxxxx.xx... 이전 1 다음
