문제 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 풀이 방법 1005번 ACM Craft와 비슷한 문제다. 위상 정렬과 DP를 활용하는 문제이므로 잘 모르겠다면 위 링크를 통해 설명을 보는 것을 추천한다. 위 문제와 차이점은 입력 형식이 다르다는 점, 모든 건물의 건설 완성 시간을 출력해야 하는 점이다. 코드 #include #include #include #include using namespace std; int main() ..
프로그래밍
문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 풀이 방법 항상 낮은 칸으로 이동하며 제일 왼쪽 위 칸에서 제일 오른쪽 아래 칸으로 갈 수 있는 경로의 개수를 구하는 문제다. 처음엔 단순한 탐색문제인 줄 알고 모든 케이스를 다 탐색해서 개수를 구하려고 했다. 하지만 최악의 경우를 생각해본다면 한 정점에서 4방향으로 모든 정점을 계속해서 탐색할 수도 있기 때문에 다른 방법이 필요하다. 좀 더 생각해보면, 어떤 점(y, x)에서 제일 오른쪽..
문제 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 풀이 방법 위상 정렬과 DP에 대해 알고 있어야 하는 문제다. 잘 모르겠다면 바킹독님 블로그나 라이님 블로그를 봐보자. (실제로 내가 알고리즘 공부를 하며 계속 방문중인 블로그들이다.) 건설 순서에 따라 위상 정렬을 진행해주면서 각 건물의 최소 건설 시작 시간을 갱신해주면 된다. 다시 말해, dp[i] = i번 건물을 짓기 시작하는 데 걸리는 최소 시간(최소 건설 시작 시간), buil..
문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 풀이 방법 1초동안 미세먼지 확산, 공기청정기 작동이 일어나며 T초 후 미세먼지의 양을 구하는 구현, 시뮬레이션 문제다. 주의할 점은 미세먼지가 확산 될 때는 그 시간의 미세먼지 양에 대해서만 처리를 해야한다. 다시말해, 확산될 때 제 자리와 확산된 방향의 A(r,c)이 변하게 되는데, 변한 값으로 확산을 처리하면 안된다. 문제에서 확산의 예시 세번째를 보면 이해가 될 것이다. 아래 코드에..
