시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB83383750.685%

문제

건축가 제이크는 계절의 대비를 테마로 한 "반전의 정원"을 설계하고 있다. 제이크는 가로 $N$, 세로 $N$짜리 정사각형 모양 땅을 확보했다. 제이크가 확보한 땅의 왼쪽 아래 꼭짓점, 오른쪽 위 꼭짓점의 좌표는 각각 $(0, 0)$, $(N, N)$이다. 제이크는 땅을 $1 \times 1$ 크기의 격자 $N^2$개로 쪼개어서 각 격자에 식물을 심으려고 한다. 제이크가 격자 $(i, j)$에 식물을 심는다면 $(i, j)$가 왼쪽 아래 꼭짓점인 $1 \times 1$ 크기의 격자 영역에 식물이 가득 찬다.

우선 제이크는 자신이 원하는 대로 산책로를 만들었다. 산책로는 관람객들이 $(0, 0)$에서 시작해서 위쪽($(x, y) \rightarrow (x, y+1)$ 방향) 또는 오른쪽($(x, y) \rightarrow (x+1, y)$ 방향)으로 $1$만큼 총 $2 \times N$번 걸어서 $(N, N)$으로 갈 수 있도록 만들어졌다. 제이크는 산책로를 기준으로 왼쪽 위 방향에 있는 격자에는 개나리를, 오른쪽 아래 방향에 있는 격자에는 코스모스를 심었다. 결과적으로 산책로는 개나리가 있는 영역과 코스모스가 있는 영역 사이의 경계선이 된다.

아직 식물이 많이 자라지 않았기 때문에 제이크는 식물이 다 자랄 때까지 기다린 다음 늦여름에 정원을 개장하려고 한다. 여름이 되면 개나리와 코스모스가 무성히 자라서 산책로를 가려버린다. 여름에는 개나리와 코스모스를 구분하기 힘들기 때문에 단순 눈대중으로는 산책로를 복원하기 어렵다. 이에 따라 제이크는 처음에 산책로의 정보를 이용하여 정원에 나무를 심은 다음, 여름에 나무의 위치를 이용하여 산책로를 복원하려고 한다. 제이크는 개나리를 심는 격자에는 벚꽃을 심을 것이고 코스모스를 심는 격자에는 단풍나무를 심을 것이다.

제이크는 자신의 예술적 감각에 따라 나무를 정확히 $K$개만 심을 것이다. 제이크를 도와 산책로가 주어지면 산책로를 복원할 수 있도록 나무를 심을 위치를 계산하는 프로그램을 작성하여라.

함수 목록 및 정의

여러분은 아래 두 함수를 구현해야 한다.

int[][] grow_tree(int K, string M)
  • $K$: 심을 나무의 수.
  • $M$: U, R로 이루어진 길이 $2 \times N$짜리 문자열. $M$은 $(0, 0)$에서 산책로를 따라 $1$만큼의 거리를 $2 \times N$번 걸었을 때 걸은 방향(위는 U, 오른쪽은 R)을 순서대로 나열한 문자열이다. $M$에서 U, R은 각각 $N$번 등장한다.
  • 이 함수는 $K \times 2$ 크기 배열 $T$를 반환해야 한다. 제이크가 $i+1$($0 \leq i < K$)번째 나무를 $(T[i][0], T[i][1])$를 왼쪽 아래 꼭짓점으로 하는 $1 \times 1$ 크기 정사각형 영역 안에 심는다. 나무의 위치가 범위를 벗어나거나 서로 겹치면 틀렸습니다를 받는다.
string restore_route(int N, int[][] T)
  • $N$: 정원의 크기.
  • $T$: $K \times 3$ 크기 배열. 제이크가 심은 $i+1$($0 \leq i < K$)번째 나무가 $(T[i][0], T[i][1])$를 왼쪽 아래 꼭짓점으로 하는 $1 \times 1$ 크기 정사각형 영역 안에 있고 나무가 벚꽃이면 $T[i][2] = 0$, 단풍나무이면 $T[i][2] = 1$이다.
  • 이 함수는 제이크가 복원한 산책로 $M$을 의미하는 길이 $2 \times N$짜리 문자열을 반환해야 한다. 해당 문자열은 grow\_tree 함수의 인자 $M$과 동일해야 정답으로 간주한다.

제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다.

여러분의 프로그램은 두 번 실행된다. 첫 번째 실행에서는 grow_tree 함수만 호출하며 두 번째 실행에서는 restore_route 함수만 호출한다. restore_route 함수의 인자 $T$는 grow_tree 함수의 반환값 $T$와 동일한 순서로 호출된다. 프로그램의 실행 시간은 두 번의 실행 시간을 합한 값이며 메모리 사용량은 두 번의 사용 메모리 중 최댓값으로 계산된다.

서브태스크

모든 데이터에 대해서, $2 ≤ N ≤ 6$을 만족한다.

번호배점제한
11

$N ≤ 2$, $K = 1$

21

$N ≤ 4$, $K = 2$

31

$N ≤ 6$, $K = 2$

예제 1

제이크가 아래 그림과 같이 정원을 만들었다고 생각해 보자. 그레이더는 grow_tree(2, "RUURRU")를 호출한다.

여러분이 grow_tree 함수에서 나무의 위치 [[1, 0], [2, 2]]를 반환하면 그레이더는 restore_route(3, [[1, 0, 1], [2, 2, 0]])을 추가로 호출한다.

여러분은 restore_route 함수에서 "RUURRU"를 반환해야 한다.

샘플 그레이더

샘플 그레이더는 첫 번째 줄에 $K$ 및 $M$을 입력받는다.

샘플 그레이더는 grow_tree 함수와 restore_route 함수를 한 번씩 호출하며, 만들어진 정원을 출력한 다음 산책 로의 성공적인 복원 여부(Correct 또는 Wrong)를 출력한다.

실제 채점에서 사용하는 그레이더는 샘플 그레이더와 다를 수 있음에 유의하여라.

출처

Contest > BOJ User Contest > FunctionCup > FunctionCup 2023 GH번

제출할 수 있는 언어

C++17, C++20, C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 예제는 채점하지 않는다.