시계태엽의 블로그

[백준] 30052번: 거리 두기 게임 [C/C++]

# 문제30052번: 거리 두기 게임 https://www.acmicpc.net/problem/30052 30052번: 거리 두기 게임격자판 위의 두 칸의 좌표를 각각 $(x_1, y_1)$, $(x_2, y_2)$라고 할 때, 두 칸 사이의 택시 거리는 $(|x_1 - x_2| + |y_1 - y_2|)$이다.www.acmicpc.net# 접근문제에서 제시된 게임을 좀 더 간단히 생각해 보자. 준성이는 두 말 사이의 거리가 최대한 작도록, 효석이는 크도록 해야 한다. 효석이가 말을 어디에 두어도 자신의 말과의 거리가 D 미만이 되게 하려면, 준성이는 최대한 격자판의 가운데에 자신의 말을 놓는 것이 최선의 선택이다. 반대로 효석이는 최대한 가장자리에 말을 두어야 한다. 특정 경우에선 준성이가 말을 최선의..

[백준] 15565번: 귀여운 라이언 [C/C++]

# 문제15565번: 귀여운 라이언 https://www.acmicpc.net/problem/15565 15565번: 귀여운 라이언꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net # 접근라이언 인형( = 1)이 k개 이상 있는 가장 작은 연속된 인형들의 집합을 찾아야 한다. 집합의 크기를 명시해 주지 않기 때문에, 이중 for문을 이용한 브루트 포스 식의 순회가 불가능하다(사실 가능하다 할지라도, N의 크기가 106이기 때문에 시간복잡도에서 걸릴 것이다). 따라서 새로운 접근 방식을 생각해야 한다. 이럴 때 필요한 것이 바로 투 포인..