Codeforces Round #504 (Div. 1 + Div. 2)

A - Single Wildcard Pattern Matching

최대 1개의 *(와일드카드)가 있는 문자열 s로 문자열 t를 표현할 수 있는 지를 묻는 문제이다.

*의 인덱스 번호를 기준으로 앞, 뒤가 문자열 t 앞과 뒤에 있으면서도

겹쳐서는 안되므로 t은 문자열의 길이는 s-1보다 작으면은 안된다.

이 두 조건에 유의하며 코드를 작성하면 풀 수 있는 문제이다.

B - Pair of Toys

1~N까지의 수 중 서로 다른 2개의 수를 골라 이들의 합이 K를 만족하는 경우의 수를 출력하는 문제이다.

N이 K-1보다 같거나 클 경우 K/2가 가능하나 K가 6일 때 (3, 3)과 같은 경우를 제외해주어야 하므로

K/2가 짝수 일 때는 1을 빼주어야 한다.

이외의 경우에는 max(0, (N-K/2))로 일반화 할 수 있다는 것을 구해내면 풀 수 있는 문제이다.

 

C - Bracket Subsequence

길이가 N인 올바른 괄호 문자열이 주어질 때 이 문자열의 부분 문자열 중 길이가 K인 올바른 괄호 문자열을 출력하는 문제이다.

괄호 문제에서 많이 이용하는 스택으로 문제를 해결하였는데 괄호가 열릴 때는 스택에 열린 괄호의 인덱스,

괄호가 닫힐 때에는 스택의 맨 위에 들어 있는 괄호의 인덱스와 닫힌 괄호의 인덱스를 체크한다.

이를 K개의 괄호가 체크 될 때까지 반복 한 뒤, 체크된 괄호의 인덱스 순서대로 출력하면 풀 수 있는 문제이다.

D - Array Restoration

N개의 숫자가 주어질 때 이 숫자들이 Q개의 쿼리를 진행하면서 만들어 질 수 있는 배열인지 확인하는 문제이다.

쿼리는 l...r의 범위에 있는 숫자들을 모두 i로 바꾸는 것이다. (이 때 i = 1 ~ Q)

먼저 가장 먼저 확인해야 할 정보는 완성된 배열에 Q라는 수는 있어야한다는 것이다.

1 ~ Q의 순서대로 쿼리를 처리하는데 Q가 이후의 쿼리에 바뀌어질 수 없기 때문이다.

배열에 0도 없고 Q도 없거나, 0이 있을 경우 첫 0 하나를 Q로 바꾸어 준다면 만족하게 할 수 있다.

또한 이 쿼리의 순서는 바뀌어질 수 없으므로 작은 수 사이에 그 수보다 큰 수가 오는 것은 가능하지만 ex) 2, 3, 3, 3, 2

큰 수 사이에 작은 수가 오는 것은 불가능하다. ex) 3, 2, 2, 2, 3

즉 완성된 배열에 수가 하나만 있을 경우에는 문제가 없지만 수가 여러 개가 있을 경우

그 수들 사이에는 자신보다 큰 수가 있어야 한다는 것을 확인해주어야 한다.

이는 전처리로 한 수가 나타난 맨 처음 인덱스, 맨 마지막 인덱스를 저장해준 뒤

배열을 앞에서부터보며 스택을 이용하여 그 수가 처음 나왔을 경우 스택에 넣어주고 그 수가 나갈 경우에는 스택에서 내보낸다.

이 때 매번 스택의 맨 위의 있는 숫자는 다음의 나오는 숫자보다 작거나 같아야 한다는 작업을 반복해 준다.

이 때 0일 경우에는 맨 앞일 경우 1, 아닐 경우 바로 전 인덱스에 있는 수로 대체하면 된다는 것을 생각해볼 수 있다.

위와 같이 코드를 작성하면 풀 수 있는 문제이다.

E - Down or Right

처음에는 처음보는 유형이라 어려울 줄 알고 건드리지 않고 있다가 건드려봤더니 생각보다 쉬웠던 문제.

N*N의 미로에서 질문을 던져 (1, 1)에서 (N, N)까지 오른쪽과 아래로만 이동하여 가는 경로를 출력하는 문제이다.

이 때 질문은 시작점과 도착점이며 이들이 오른쪽과 아래로만 이동하여 갈 수 있는 지 대답하여 준다.

그 대신 시작점과 도착점의 두 좌표의 맨해튼 거리는 N-1보다 같거나 커야한다.

이 문제의 접근 방법은 한 좌표에서 이동방법은 아래 또는 오른쪽 뿐이라는 것이다.

(1, 1) ~ (N, N)이 이동가능한 미로에서 (2, 1) ~ (N, N), (1, 2) ~ (N, N)를 갈 수 있는 지에 대한 질문을 통하여

둘 중 하나의 방법은 무조건 YES가 나오므로 YES가 나오는 좌표로 이동하면서 반복적으로 진행한다.

이 때 맨해튼 거리가 N-1보다 같거나 커야하므로 점점 도착점과 가까워진다면 질문을 할 수 없는데

이 때는 뒤에서부터 경로를 측정한다. 즉 (1, 1) ~ (N, N-1), (1, 1) ~ (N-1, N) 중 YES인 경로를 통하여 이동한다.

이 때 주의해주어야 할 점은 시작점에서 아래쪽으로 가는 것을 우선으로 했다면,

도착점에서는 오른쪽으로 가는 경로를 우선적으로 보아야한다는 것이다.

이렇지 않을 경우 시작점, 도착점에서 구한 경로가 만나지 않을 수 있기 때문이다. ex) 벽이 없는 4*4 미로.

(N-1)*2의 경로를 모두 찾았을 경우 출력형식에 맞게 출력해주면 풀 수 있는 문제이다.

F - Mobile Phone Network

X

G - Pisces

X