주간 문제풀이 17 (BOJ 16741 / 16742)

BOJ 16741 - Emergency Evacuation

https://www.acmicpc.net/problem/16741

16741번: Emergency Evacuation

자동차 좌석에 사람이 앉아있고, 사람당 한 칸씩 서로의 자리를 차지하지 않는 방식으로 움직였을 때, 가장 빨리 나갈 수 있는 시간.

풀이:

뭔가 시뮬레이션을 해야 풀 수 있을 것 같이 생겼지만, 사실 시뮬레이션 없이 그리디로 풀 수 있다.

 

우선, 딱 한 사람만 존재한다고 할 때 그 사람이 나가는 데 몇 개의 스텝이 필요한지는 쉽게 구할 수 있다. 이때 한 스텝당 한 사람만 출구를 통해 나갈 수 있음을 관찰하자. 따라서 여러 사람이 있을 때는, 각각의 사람이 다른 사람이 없을 때 나가는 데 필요한 스텝 숫자를 각각 구한 후, 같은 스텝에 겹치는 사람의 숫자만큼 실제로 나가게 되는 스텝이 뒤로 미뤄진다고 생각하면 된다.

 

코드: http://boj.kr/0066990f3e414488a6e8ea14b264cc91

 

BOJ 16742 - Shortest Common Non-Subsequence

https://www.acmicpc.net/problem/16742

16742번: Shortest Common Non-Subsequence

문제: 두 개의 0과 1로 이루어진 문자열이 주어지면, 그 두 문자열의 subsequence가 모두 아닌 문자열 중, 가장 짧은 문자열들 중에 사전순으로 가장 작은 문자열을 찾는 문제.

 

풀이:

우선 사전순을 고려하지 않고, 가장 짧은 문자열의 길이만 구한다고 생각해보자. 이를 위해 아래 dp식을 생각해보자. "dp[i][j] = 지금 어떤 문자열이 A[0:i]와 B[0:j]에 대한 subsequence라고 할 때, 그 문자열에 몇 개의 문자를 추가해야 non-subsequence가 되는가?" 이 때 우리가 원하는 답은 dp[0][0]이고, A와 B의 각 위치마다 다음 0과 1을 미리 찾아두는 전처리를 통해 이 dp식을 N^2에 구할 수 있다.

 

이제 사전순을 고려하기 위해서는, 답 문자열에 순서대로 글자를 하나씩 추가해보면 된다. 0을 추가한 후 도달한 dp값이 여전히 최적이라면 0을 선택하고, 아니면 1을 선택하는 식으로 추가하면 된다.

 

코드: http://boj.kr/bed2084677b14919a97e1eb4bcaf70cd