Future is now

https://www.acmicpc.net/problem/16932 16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 www.acmicpc.net 주어진 지도에서 1이 들어있는 칸끼리 연결한 것을 모양이라고 하는데, 지도의 칸에 들어있는 수를 변경해서 모양의 최대 크기를 구하는 문제입니다. 지도는 0, 1로만 구성되어 있는데요. 1을 0으로 바꾸면 모양의 크기는 무조건 줄어들기 때문에 0에서 1로 바꿔는 쪽으로만 생각합니다. 단순히 생각해서 한 칸씩 바뀔 때마다 그룹의 최대 크기를 구해본다고 했을 때, 시간복잡도는 \(O(NM*N..

https://www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려 www.acmicpc.net 돌 그룹 3가지가 있는데 이 3가지 그룹의 돌 개수를 같게 할 수 있는지를 찾는 문제입니다. 각 그룹의 돌 개수를 정점이라고 생각하면 BFS로 풀 수 있습니다. 점화식은 d[a][b][c]로 정할 수 있는데, 전체 돌 개수를 구한 sum = a + b + c 값을 이용하면 굳이 3차원 배열이 아닌 d[a][b]인 2차원 배열으로도 문제를 해결 할 수 있습니다. 점화식 d[i][j] : 첫 번..

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 건물 층을 엘리베이터로 방문하는데 목적층에 도달하기 위해 엘리베이터 버튼을 적어도 몇 번 눌러야 하는지 구하는 문제입니다. 적어도라는 말은 최소로 버튼을 눌러보는 것으로 바꿔서 생각할 수 있습니다. 최소로 버튼을 눌러서 각 층을 방문한다고 생각할 수 있는데 각 층을 정점이라고 생각해 보면, BFS로 문제를 해결하면 되겠습니다. 각 층에 방문할 때 dist 배열에는 최소로 버튼을 누르는 횟수를 저장하면서, 동시..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 수빈이가 동생 위치에 도달하기까지 주어진 조건을 만족하며 최소로 걸리는 시간을 구하는 문제입니다. 수빈이의 현재 위치를 x라고 할 때, 움직일 수 있는 행동으로는 1. 순간이동 x → 2 * x (소요시간:0초) 2. 앞으로 이동 x → x + 1 (소요시간:1초) 3. 뒤로 이동 x → x - 1 (소요시간:2초) 이렇게 3가지 입니다. 우선, 수빈이의 처음 시..