🔗 문제
https://www.acmicpc.net/problem/17780
✏️ 풀이
문제 풀이는 구현.
조건을 정리하려고 했으나 문제에서 친절히 알려주고 있어서 생략 하겠습니다.
이번에도 큰 틀을 아래처럼 잡고 세부 조건을 채워갔습니다.
int getAnswer()
{
int answer = 0;
while(++answer > 1000)
{
for(int i=0; i<K; ++i)
{
// 체스말 1개가 이동 한 후,
// 한 자리에 말이 4개 이상이면 answer을 리턴한다.
}
}
return -1;
}
어떤 자료 구조를 사용했는지가 중요한 문제라고 생각합니다.
이 문제는 상어 시리즈처럼 보이지만 상어와 달리 한 칸에 위치한 요소들의 순서도 필요하고,
0.5초라는 시간 제한에 문제 풀이상 빈번한 삽입/삭제 연산의 시간 복잡도가 중요하기 때문입니다.
- 맨 밑의 체스말만 이동할 수 있기 때문에 O(1)로 맨 밑의 요소가 무엇인지 판단할 수 있는 자료구조를 생각하자.
- 자료구조의 사이즈가 유동적으로 바뀌어도 오버헤드가 심하지 않는 자료구조여야 한다.
- RED, BLUE, WHITE 조건에 의해 자료구조에 저장된 맨 앞, 맨 뒤로 요소를 사용할 수 있어야 한다.
이런 조건들로 인해 deque를 사용해주었습니다.
[ 변수 ]
- int board[][] : 절대 변하지 않는 체스판의 컬러
- deque<int> state [][] : 체스판의 위치마다 말의 고유번호를 deque로 저장한다.
자료구조가 중요하다는 말 취소!!!
굳이 deque를 쓰지 않아도 된다.
왜냐하면 각 위치의 가장 위, 가장 밑만 알면 되기 때문에 deque가 아니라 하나의 구조체로 관리할 수 있다.
-스터디하면서 남의 코드로 배움-