본문 바로가기

전체 글

 (125)
17472 다리 만들기 2 정답 코드를 보아도 이해가 안된 문제였다.. 접근의 핵심은 모든 섬을 연결했을 때의 최소 거리이며, 이 부분에서 MST가 생각나지 않았다. 처음 시도는 dfs로 모든 섬을 연결할 수 있는지 판단하면 어떨까 했는데 연결 부분에서 막혔다. 서론은 여기까지 하고 문제를 분석해보면 접근 방법은 다음과 같다. 1. 각각의 섬을 구분해주기 위해 BFS 혹은 DFS로 넘버링한다. 1.1 여기서 섬을 넘버링 해주는 이유는 뒤에 나올 크루스칼 알고리즘을 사용하기 위함이다. 2. 반복문으로 1인 칸마다 연결할 수 있는 다리를 각 방향마다 계산하여 벡터에 저장한다. 3. 2에서 구한 다리들을 가지고, 크루스칼 알고리즘을 수행한다. 3.1 수행하면서 다리를 놓을 때의 길이를 답에 더한다. 고찰 : 내가 생각하지 못했던 점은 ..
16235 나무 재테크 www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 문제의 조건들을 잘 지켜서 구현하는 시뮬레이션 문제이다. 이 문제에서 예제 8이 77이 나와서 고생했었는데, 이 경우 가을에 번식되는 나무가 하나가 아니라는 것만 유의하여 구현하면 해결된다! 이제 문제를 살펴보자. 얼핏 보면 나이가 어린 나무부터 정렬해야 할 것 같은 느낌인데, 정렬 없이 구현할 수 있다. 1. 문제의 조건 중에 입력으로 주어지는 나무엔 겹치는 경우가 없다. 2. 나이가 어린 나..
1, 2, 3 더하기 시리즈 1, 2, 3 더하기 시리즈는 DP 문제의 감을 잡기 좋은 것 같다. 푸는 문제마다 업데이트 할 예정이고, 푼 문제들을 정리할 겸 어떻게 접근하는지 간략하게 적어본다. 각 문제마다 Top Down, Bottom up 두 가지 방식으로 풀어보는걸 추천한다. 1, 2, 3 더하기 n의 크기가 작기 때문에 메모이제이션을 쓰지 않아도 풀리는 문제이다. 1, 2, 3 더하기 3 접근 : n의 크기가 10^6이기 때문에 모든 경우를 다 계산하면 시간초과가 발생한다. 잘 생각해보면, 답을 구하는데 부분 문제가 겹치는걸 알 수 있다. 풀이 : 점화식을 세워보면 다음과 같다. dp[N] = dp[N - 1] + dp[N - 2] + dp[N - 3] 1, 2, 3 더하기 4 접근 : 순서와는 상관 없이 사용된 수의 개수..

티스토리툴바