본문 바로가기
반응형

Problem Solving242

백준 14938번 서강그라운드 - 스위프트(Swift) 풀이 1. 모든 정점에 대해 각 정점에서 모든 정점으로 가는 거리를 플로이드 와샬 알고리즘을 사용하여 구한다. 2. 모든 정점에 대해 해당 정점과의 거리가 m이하인 정점들을 탐색하여 해당 정점에 낙하했을 때 얻을 수 있는 아이템 수를 구한다. 3. 2번에서 구한 값 중 최댓값을 출력한다. 1. 모든 정점에 대해각 정점에서 모든 정점으로 가는 거리를 플로이드 와샬 알고리즘을 사용하여 구한다. 각 정점에 낙하하는 모든 경우를 고려한 뒤 최적해를 골라야 한다. 또한, 어떤 정점에 낙하했을 때 얻을 수 있는 아이템 수를 알려면, 해당 정점에서 나머지 정점으로의 거리를 전부 알아야 한다. 따라서 모든 정점에 대해 나머지 정점으로의 거리를 구하는 플로이드 와샬 알고리즘을 사용한다. N=100이므로 O(N^3)도 제한시간.. 2022. 1. 26.
백준 17070번 파이프 옮기기 1 - 스위프트(Swift) 풀이 1. dp(row, col, direction) = 왼쪽 끝이 (row,col)에 위치하고 direction 방향으로 놓인 파이프를 (N,N)으로 옮기는 방법의 수 2. dp(row, col, direction) = ∑ dp(파이프가 이동할 수 있는 위치, 방향) 1. dp(row, col, direction) = 왼쪽 끝이 (row,col)에 위치하고 direction 방향으로 놓인 파이프를 (N,N)으로 옮기는 방법의 수 DP라는 방법만 떠올리고 나면 특별히 고려해줄 점 없이 그냥 구현하면 된다. dp(row, col, direction)을 위와 같이 정의한다. 2. dp(row, col, direction) = ∑ dp(파이프가 이동할 수 있는 위치, 방향) 파이프를 이동시킬 수 있는 모든 방법을 .. 2022. 1. 26.
백준 15686번 치킨 배달 - 스위프트(Swift) 풀이 1. M개 이하의 치킨집을 고르는 모든 경우에 대해 도시의 치킨 거리를 계산한다. 1. M개 이하의 치킨집을 고르는 모든 경우에 대해 도시의 치킨 거리를 계산한다. 단순 구현 문제이다. 브루트포스로도 시간 안에 풀 수 있다. M개 이하의 치킨집을 이미 골랐다고 가정했을 때, 도시의 치킨 거리를 구하는 데는 O(2N * 13)이 든다. M개 이하의 치킨집을 고르는 경우의 수는 적어도 2^13보다는 적으므로 최종 시간 복잡도는 O(2N * 13 * 2^13) = O(2^14 * 13 * N)이고, N=50이므로 연산 횟수 10,649,600으로 AC를 받기에 충분한 시간 복잡도이다. import Foundation typealias Chicken = (row: Int, col: Int) typealias C.. 2022. 1. 25.
백준 17352번 여러분의 다리가 되어 드리겠습니다! - 스위프트(Swift) 풀이 1. 모든 다리에 대해 다리로 이어진 두 섬을 union 한다. 2. 1번 섬과 이어지지 않은 섬, 즉 find(i) ≠ find(1)인 섬을 찾아 (1, i)를 출력한다. 1. 모든 다리에 대해 다리로 이어진 두 섬을 union 한다. 다리로 이어진 두 섬은 왕복할 수 있다. 1 - 2가 연결되어 있고, 1 - 3이 연결되어 있으면 2 - 3으로도 갈 수 있다. union 연산과 같다. 2. 1번 섬과 이어지지 않은 섬, 즉 find(i) ≠ find(1)인 섬을 찾아 (1, i)를 출력한다. 어떤 두 섬이든 다리로 왕복할 수 있으려면 1번 섬에서도 어느 섬으로든 갈 수 있어야 한다. 따라서 1번 섬과 부모가 다른 섬을 찾아 출력해주면 된다. 1번 섬이 아니더라도 아무 섬이나 하나 기준으로 잡고, 그 .. 2022. 1. 25.
백준 2718번 타일 채우기 - 스위프트(Swift) 풀이 + 그림 설명 1. dp(n, state) = n번째 열의 상태가 state일 때, n번째 열부터 마지막 열까지 채우는 방법의 수 2. state는 n열의 1~4행의 상태를 비트마스크로 나타낸 것이고, 0~16 중 하나의 값을 갖는다. 3. dp(n, state) = ∑ dp(n+1, 주어진 state에서 만들 수 있는 다음 열의 상태) 1. dp(n, state) = n번째 열의 상태가 state일 때, n번째 열부터 마지막 열까지 채우는 방법의 수 왼쪽 열부터 차례로 채워나간다. 최종적으로 구해야 하는 것은 dp(1, 0)이다. 2. state는 n열의 1~4행의 상태를 비트마스크로 나타낸 것이고, 0~16 중 하나의 값을 갖는다. n번째 열을 채우려면 n-1번째 열을 채우면서 n번째 열이 어떤 상태가 되었는지 알.. 2022. 1. 25.
반응형

티스토리툴바