보드게임 컵

https://www.acmicpc.net/contest/view/927

보드게임컵

 

이번 대회에서 5솔을 했다.

1시간 뒤에 들어간 것과, D번에서 진짜 바보같은 실수를 한 것 때문에 잘 못 했다.

A  - 노 땡스!

단순 구현 문제

AC - 1:02

소스 코드

 

B - 할리갈리

map 자료구조를 사용하면 쉽게 풀림

(map을 쓰지 않고, 입력받은 문자열의 앞글자 만으로도 풀림)

AC - 1:04

소스 코드

 

C - 크레이지 타임

이 문제 또한 단순 구현 문제이다

AC - 1:18

소스 코드

 

 

D - Yacht Dice

이 문제가 이번 대회의 문제점이었다.

문제 자체는 그냥 단순 구현 문제였다.

하지만 바보같이 i와 j를 바꿔쓴 탓에 계속 WA를 받고 있엇다.

이것을 발견하기까지 1시간 반 가까이 걸렸다..

9 - WA

AC - 2:50

소스 코드

 

N - 수 나누기 게임

D번을 풀고 멘탈이 나갔었다.

그래서 그냥 침대에 누워서 대회는 끝낼려 했는데,

5문제를 솔브를 하면 배경을 준다는게 생각이나 부랴부랴 다시 문제를 잡았다.(대회 종료 30분전)

스코어 보드를 보니 N이 많이 풀렸어서 잡았다

이 문제를 보고 어떻게 O(n^2)이 아닌 O(nlogn)이나 O(n)으로 풀 수 있을까 생각에 잠겼다.

그러다 약수를 구하는데 O(n^(1/2))이 드는 알고리즘이 생각이 났고, 이 알고리즘과 맵 자료구조를 사용하여 구현했다.

1- WA.

하지만 한 번 틀렸었는데, 이 문제도 똑같이 i와 j를 바꿔써서 틀렸던 것이였다..

그래도 금방 찾아서 고쳐서 맞췄다.

AC - 3:56

소스 코드

 

여기까지가 대회에서 푼 문제들이다.

 

 

대회가 끝나고 G번 까지 풀어봤다.

 

G - 모든 곳을 안전하게

Case-work문제였다.

각 칸에 있는 말의 개수가 1개인 칸이 몇개인지로 분류해주면 된다

먼저 1개인 칸의 개수를 K라고 했을 때,

 

K >= 3일 때는 무조건 NO를 출력한다.

칸에 1개인 경우가 무조건 생기기 때문이다

 

K = 2일 때는 

두 칸의 길이가 정확히 X일 경우에만 가능하다.

 

K = 1일 때는

칸에 말이 하나가 있는 칸에서 + X를 한 칸에 말의 개수가 2개 이상이거나

- X를 한 칸에 말의 개수가 3개 이상일 경우에만 가능하다.

 

K = 0일 때는

ai의 칸의 개수는 3개 이상이고, a(i+x)의 칸에는 2개 이상인 경우에만 가능하다.

 

대회에서 20분만 시간이 더 있었다면 풀었을 텐데..

 

소스 코드