끝없이 넓은 바닥에 타일이 깔려 있고, 처음에는 모든 타일이 흰색이다.
타일의 자리는 정수 두 개 (x, y)로 나타낸다. 오른쪽으로 갈수록 x가 커지고, 위로 갈수록 y가 커진다.
로봇은 (0, 0) 타일에서 출발한다. 출발할 때 서 있는 타일은 뒤집히지 않는다.
명령 n개가 차례로 주어진다. 명령 하나는 방향과 걸음 수 k이고, 로봇은 그 방향으로 한 걸음에 한 타일씩 k걸음 가려고 한다. 방향은 U(위), D(아래), L(왼쪽), R(오른쪽) 가운데 하나이다.
로봇이 한 걸음 옮겨 밟은 타일이 흰색이면 그 타일은 검은색으로 바뀌고, 로봇은 남은 걸음을 이어 간다.
밟은 타일이 검은색이면 그 타일은 흰색으로 바뀌고, 로봇은 그 타일에 선 채로 그 명령의 남은 걸음을 버린다. 다음 명령은 그 자리에서 시작한다.
모든 명령이 끝난 뒤 검은색 타일의 수와 로봇이 서 있는 자리를 출력하라.
입력
첫 줄에 n이 주어진다. 다음 n줄에 명령이 한 줄에 하나씩, 방향 글자와 k가 빈칸 하나로 나뉘어 주어진다. 1 ≤ n ≤ 2,000, 1 ≤ k ≤ 9,000이고, 모든 명령의 k를 더한 값은 9,000 이하이다
출력
첫 줄에 검은색 타일의 수, 둘째 줄에 로봇이 서 있는 자리의 x와 y를 빈칸 하나로 띄워 출력
예시 1 · stdin
3
R 3
L 5
R 2
stdout
1
3 0
예시 2 · stdin
6
R 11
U 10
L 10
D 12
L 3
R 5
stdout
41
-1 0
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
검은 타일의 자리를 집합에 넣고, 밟을 때마다 들어 있는지 물어요(Python in, JS has, Java contains, C# Contains, C++ find, 크레이콘 있나). 어려운 점은 수 두 개짜리 자리를 원소 하나로 넣는 방법이 언어마다 다르다는 거예요. Python은 튜플 (x, y)를, C#은 튜플을 HashSet<(int, int)>에, C++은 pair를 std::set에 그대로 넣으면 값으로 견줘요(C++ unordered_set은 pair의 해시가 없어서 그대로는 컴파일되지 않아요). Java는 record를 만들면 equals와 hashCode가 값 기준으로 생겨요. JS·TS와 크레이콘은 문자열 "x,y"로 바꿔 넣는데, 크레이콘은 사전()의 열쇠를 집합처럼 쓰고 빼기로 지워요. C에는 집합이 없어서 자리를 배열에 모아 두고 처음부터 찾아요. 걸음이 9,000번뿐이라 그래도 충분히 빨라요. 함정 하나: JS·TS의 Set에 배열 [x, y]를 넣으면 내용이 같아도 서로 다른 원소로 쳐서 has가 늘 false예요. 예시 1에서 검은 타일을 한 번도 알아보지 못해 10과 0 0이 나와요. Java의 HashSet<int[]>와 C#의 HashSet<int[]>도 똑같이 false를 줘요. 함정 둘: Python에서 집합에 목록 [x, y]를 넣으면 TypeError(unhashable type: 'list')로 멈춰요. 바뀔 수 있는 목록 대신 튜플을 써야 해요. 함정 셋: 문자열 열쇠를 만들 때 사이 글자 없이 이으면 서로 다른 자리가 같은 열쇠가 돼요. 예시 2에서 (11, 0)과 (1, 10)이 둘 다 "110"이라, 흰 타일 (1, 10)을 검은 타일로 잘못 알고 멈춰서 41이 아니라 39가 나와요.
Pythonmain.py · 20 줄
import sysMOVES = {"U": (0, 1), "D": (0, -1), "L": (-1, 0), "R": (1, 0)}lines = sys.stdin.read().split("\n")n = int(lines[0])black = set() # 검은 타일의 자리 (x, y)x = y = 0for line in lines[1:n + 1]: d, k = line.split() dx, dy = MOVES[d] for _ in range(int(k)): x += dx y += dy if (x, y) in black: black.remove((x, y)) # 검은 타일: 흰색으로 뒤집고 남은 걸음을 버린다 break black.add((x, y)) # 흰 타일: 검은색으로 뒤집고 이어 간다print(len(black))print(x, y)
JavaScriptmain.js · 23 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);const MOVES = { U: [0, 1], D: [0, -1], L: [-1, 0], R: [1, 0] };// 배열 [x, y]는 내용이 같아도 다른 원소로 치므로, 문자열 "x,y"를 넣는다const black = new Set();let x = 0;let y = 0;for (let i = 1; i <= n; i++) { const [d, k] = lines[i].trim().split(" "); const [dx, dy] = MOVES[d]; for (let step = 0; step < Number(k); step++) { x += dx; y += dy; const key = `${x},${y}`; if (black.has(key)) { black.delete(key); // 검은 타일: 흰색으로 뒤집고 남은 걸음을 버린다 break; } black.add(key); // 흰 타일: 검은색으로 뒤집고 이어 간다 }}console.log(black.size);console.log(`${x} ${y}`);
TypeScriptmain.ts · 25 줄
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const n: number = Number(lines[0]);const MOVES: Record<string, [number, number]> = { U: [0, 1], D: [0, -1], L: [-1, 0], R: [1, 0] };// 배열 [x, y]는 내용이 같아도 다른 원소로 치므로, 문자열 "x,y"를 넣는다const black = new Set<string>();let x = 0;let y = 0;for (let i = 1; i <= n; i++) { const [d, k]: string[] = lines[i].trim().split(" "); const [dx, dy]: [number, number] = MOVES[d]; for (let step = 0; step < Number(k); step++) { x += dx; y += dy; const key: string = `${x},${y}`; if (black.has(key)) { black.delete(key); // 검은 타일: 흰색으로 뒤집고 남은 걸음을 버린다 break; } black.add(key); // 흰 타일: 검은색으로 뒤집고 이어 간다 }}console.log(black.size);console.log(`${x} ${y}`);
JavaMain.java · 40 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.HashSet;import java.util.Set;public class Main { // record는 equals와 hashCode를 값으로 만들어 주므로 집합에 그대로 넣을 수 있다 record Tile(int x, int y) {} public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine().trim()); Set<Tile> black = new HashSet<>(); int x = 0, y = 0; for (int i = 0; i < n; i++) { String[] parts = in.readLine().trim().split(" "); int dx = 0, dy = 0; switch (parts[0]) { case "U" -> dy = 1; case "D" -> dy = -1; case "L" -> dx = -1; default -> dx = 1; } int k = Integer.parseInt(parts[1]); for (int step = 0; step < k; step++) { x += dx; y += dy; Tile tile = new Tile(x, y); if (black.contains(tile)) { black.remove(tile); // 검은 타일: 흰색으로 뒤집고 남은 걸음을 버린다 break; } black.add(tile); // 흰 타일: 검은색으로 뒤집고 이어 간다 } } System.out.println(black.size()); System.out.println(x + " " + y); }}
C#Main.cs · 39 줄
using System;using System.Collections.Generic;class Program{ static void Main() { int n = int.Parse(Console.ReadLine().Trim()); // 튜플 (x, y)는 값이 같으면 같은 원소다 var black = new HashSet<(int, int)>(); int x = 0, y = 0; for (int i = 0; i < n; i++) { string[] parts = Console.ReadLine().Trim().Split(' '); int dx = 0, dy = 0; switch (parts[0]) { case "U": dy = 1; break; case "D": dy = -1; break; case "L": dx = -1; break; default: dx = 1; break; } int k = int.Parse(parts[1]); for (int step = 0; step < k; step++) { x += dx; y += dy; if (black.Contains((x, y))) { black.Remove((x, y)); // 검은 타일: 흰색으로 뒤집고 남은 걸음을 버린다 break; } black.Add((x, y)); // 흰 타일: 검은색으로 뒤집고 이어 간다 } } Console.WriteLine(black.Count); Console.WriteLine($"{x} {y}"); }}
C++main.cpp · 36 줄
#include <iostream>#include <set>#include <utility>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; // pair는 값으로 견주므로 std::set에 그대로 넣을 수 있다 set<pair<int, int>> black; int x = 0, y = 0; for (int i = 0; i < n; i++) { char d; int k; cin >> d >> k; int dx = 0, dy = 0; if (d == 'U') dy = 1; else if (d == 'D') dy = -1; else if (d == 'L') dx = -1; else dx = 1; for (int step = 0; step < k; step++) { x += dx; y += dy; auto it = black.find({x, y}); if (it != black.end()) { black.erase(it); // 검은 타일: 흰색으로 뒤집고 남은 걸음을 버린다 break; } black.insert({x, y}); // 흰 타일: 검은색으로 뒤집고 이어 간다 } } cout << black.size() << '\n' << x << ' ' << y << '\n'; return 0;}
Cmain.c · 49 줄
#include <stdio.h>#define MAXSTEPS 9000/* C에는 집합이 없다. 검은 타일의 자리를 배열에 모아 두고 처음부터 찾는다. 걸음이 많아야 9,000번이라 검은 타일도 9,000개를 넘지 않는다. */static int bx[MAXSTEPS], by[MAXSTEPS];static int count = 0;/* (x, y)가 든 칸 번호를 돌려준다. 없으면 -1 */static int find(int x, int y) { for (int i = 0; i < count; i++) { if (bx[i] == x && by[i] == y) return i; } return -1;}int main(void) { int n; scanf("%d", &n); int x = 0, y = 0; for (int i = 0; i < n; i++) { char d; int k; scanf(" %c %d", &d, &k); int dx = 0, dy = 0; if (d == 'U') dy = 1; else if (d == 'D') dy = -1; else if (d == 'L') dx = -1; else dx = 1; for (int step = 0; step < k; step++) { x += dx; y += dy; int at = find(x, y); if (at >= 0) { /* 검은 타일: 마지막 칸을 그 자리로 옮겨 지우고, 남은 걸음을 버린다 */ count--; bx[at] = bx[count]; by[at] = by[count]; break; } bx[count] = x; /* 흰 타일: 검은색으로 뒤집고 이어 간다 */ by[count] = y; count++; } } printf("%d\n%d %d\n", count, x, y); return 0;}
Craykonmain.cray · 43 줄
n = 콘솔.줄읽기().수로변환();// 사전의 열쇠를 집합처럼 쓴다. 자리는 문자열 "x,y"로 바꿔 넣는다black = 사전();x = 0;y = 0;반복 (i = 0; i < n; i++){ parts = 콘솔.줄읽기().공백제거().나누기(); dx = 0; dy = 0; 선택 (parts[0]) { 경우 "U": dy = 1; 그만; 경우 "D": dy = -1; 그만; 경우 "L": dx = -1; 그만; 그밖에: dx = 1; 그만; } k = parts[1].수로변환(); 반복 (step = 0; step < k; step++) { x += dx; y += dy; key = x + "," + y; 만약 (black.있나(key)) { // 검은 타일: 흰색으로 뒤집고 남은 걸음을 버린다 black.빼기(key); 그만; } // 흰 타일: 검은색으로 뒤집고 이어 간다 black[key] = 참; }}콘솔.쓰기(black.개수);콘솔.쓰기(x + " " + y);