joseph0528 코딩 블로그

이 문제는 노드 간 거리가 정해진 트리가 있을 때, 각 트리의 노드에서 거리 d만큼을 선택하거나 취소할 수 있는 쿼리가 주어진다.이때 쿼리마다 1번 노드에서 N번 노드까지 모두 선택되어 있는지를 쿼리마다 출력하는 문제이다.Q개의 쿼리에서 1 A B 가 들어오면 A에서 B만큼의 거리가 선택되는 것이고, 2 C 가 주어지면 C번째 시나리오(선택 쿼리)가 선택 해제가 된다.이 트리는 문제의 예제를 나타낸 것이다. 그 다음에 쿼리를 하나씩 진행해 보자.이렇게 계속 진행해 보자.5번 쿼리까지 진행한 모습이다. 아직 1에서 11까지 도달하지 못했기 때문에 NO를 출력한다.그럼 이제 6번 쿼리를 해보자. 6번 쿼리까지 진행하면 1부터 11까지 모두 선택이 가능하기 때문에 YES를 출력한다. 이후 7,8,9 번 쿼리..

이 문제를 요약하면 1번 점에서 N까지 갈 때 특정 시간 때에만 움직이며, 움직이지 않을 때는 숨을 수 있는 노드에 있어야 된다는 것이다.즉 자신을 숨길 수 없는 지점은 도로의 일부로서 취급해주고, 다익스트라를 진행해 주면 된다. N의 범위가 2000 이므로 O(N^2logN) 으로 모든 점간의 거리를 계산해 준다.그 뒤에 두 점간의 거리가 특정 시간대에 해당되는지를 봐주면 된다. 만약 거리가 움직일 수 없는 시간대를 포함하게 된다면, 그 도로는 N까지 도달할 수 없게 된다. 그러므로 두 점 사이 거리가 a(문제에서 주어진 입력) 보다 같거나 작은 경우만 저장해 준다.또 거리가 되더라도 자신을 숨길 수 없는, 즉 C_i = 1 인 지점의 경우 a이내에 도달하더라도 몸을 숨길 수 없기 때문에 새롭게 만들어..

이 문제는 dp를 많이 풀어봤다면 바로 dp임을 알 수 있는 문제이다.dp 임을 알았으면 점화식이 어떻게 되는지 찾아야 되는데, 해당 조건을 봤을 때 전형적인 배낭문제와 비슷한 꼴로 구현해 주면 된다는 것을 파악할 수 있다.대신 사람이 2명이므로, 2차원으로 2명의 위치를 관리하면서 코드를 구현해주면 된다. dp [i][j]를 1번 사람이 i 위치에, 2번 사람이 j위치에 있다고 할 때 최솟값이라고 한다면, dp[i][j] 는 4 * 4 = 16 가지의 경우의 수를 모두 보면서 조건에 맞을 경우만 dp[i][j] 의 최솟값을 업데이트해주면 된다.여기서 유의할 점은 묶음권의 경우 1번, 2번 사람 모두 같은 기간에 적용되는 것이기 때문에 i == j 일경우에만 적용해 줘야 된다. 이를 코드로 구현하면 A..