https://www.acmicpc.net/problem/25200
25200번: 곰곰이와 자판기
$f(k)$ 가 음료수 종류 $k$ 가 $M$ 번의 차원 이동을 거쳐 최종적으로 변하는 음료수 종류라고 할 때, $f(1), f(2), \cdots, f(N)$ 을 첫 번째 줄에 공백을 사이에 두고 출력하라.
www.acmicpc.net
애드혹 문제였습니다.
음료수는 순서대로 현재상태에서 다른상태로 전이됩니다. 처음에 1~N의 번호를 가진 음료수 N개가 있고 순서대로 주어지는 전이에 따라 변한다고 생각하시면 될 것 같습니다. 문제에서 요구하는 것은 1~N번을 가진 N개의 음료수가 최종적으로 어떻게 변할 것인가에 대한 문제입니다.
N과 전이의 횟수인 M 모두 300000이므로 처음부터 시작하여 각 전이마다 N개의 음료수를 전부 체크하여 변화시킬 수 없습니다. 따라서 조금 발상이 필요합니다.
예를 들어 맨마지막에 2번 음료수를 전부 4번음료수로 변화시키는 전이가 주어졌다고 생각해봅시다. 현재 2번음료수였던 음료수들은 전부 4번으로 변할 것입니다.
즉 이전에 전이에의해 2번음료수가 되었던 음료수들도 전부 4번으로 변하는 것입니다. 일단 2번음료수가 4번으로 변한 사실을 기록해 봅시다. 다른 음료수가 2번음료수로 변한 전이 또한 앞선 순서에 기록되어 있을것입니다. 하지만 우리는 2번음료수가 최종적으로 4번으로 변한다는 사실을 기록했습니다. 따라서 2번음료수로 변하는 음료수들 또한 4번으로 변한다는 것을 알 수 있습니다. 이처럼 역순으로 M번의 차원이동을 확인할경우 O(M)시간내에 N개의 음료수들의 최종적으로 변하는 음료수를 알 수 있을것입니다.
'PS > boj' 카테고리의 다른 글
| 백준 20437 문자열 게임 2 (0) | 2023.01.06 |
|---|---|
| 백준 11952 좀비 (0) | 2023.01.05 |
| 백준 24229 모두싸인 출근길 (0) | 2023.01.04 |
| 백준 20168 골목 대장 호석 - 기능성 (0) | 2023.01.03 |
| 백준 6987 월드컵 (0) | 2023.01.02 |