[백준] 26005번 나뭇잎 학회 [Python]

728x90

NxN개의 스위치 중에서 단 하나만 있는 정상 스위치는 상하좌우 중 하나의 스위치와 같이 한 번 누르면 작동한다.

어떠한 경우에도 정상 스위치를 구할 수 있는 최소한으로 누러야 하는 횟수를 구하는 문제

문제

기선이는 퀴즈를 좋아해서 알고리즘 학회에 들어가고자 하이아크에 방문하였다. 하지만 학회 문 앞에는 단 한 개의 전구, 여러 개의 스위치와 함께 다음과 같은 쪽지가 붙어있었다.

보이는 것과 같이 하나의 전구와 개의 스위치가 배열로 있습니다.
이 스위치 중 단 하나만 전구와 연결되어 있으며, 연결된 스위치를 누르면 전구가 깜빡입니다.
스위치에는 특수 장치가 적용되어 있어서 상하좌우로 인접한 두 개의 스위치를 동시에 눌러야만 합니다.
예를 들어 일 때, 당신이 번 스위치를 누르고 싶다면 인접한 스위치 상$()$, 하$()$, 좌$()$, 우$(6)$ 중 하나의 스위치와 같이 한 번에 눌러야 합니다.

'너무 쉽잖아' 생각하고 스위치를 누르려는 순간, 밑에 작게 쓰여있는 글씨를 보고 경악하고 말았다.

귀찮음이 많은 기선이는 밖에서 최소한의 나뭇잎만 주워오려고 한다. 어떤 경우에도 정답을 맞히는 데 필요한 나뭇잎의 최소 개수를 여러분이 대신 구해보자.

N 이 주어진다. $(1≤N≤1000)$

어떤 경우에도 정답을 맞히는 데 필요한 나뭇잎의 최소 개수를 출력한다.

n=1일때, 0 $($안 눌러도 알 수 있음$)$

짝수일 때,

모든 스위치에 숫자를 메기고 안 겹치게 숫자 두 개 씩 짝을 지으면서 확인

만약 마지막에 두 개가 남을 때까지 불이 안 켜지면, 남은 두 개 중 하나랑 이미 눌렀던 다른 숫자$($상하좌우에 있는$)$를 누르면 확인 가능 -> 제곱의 절반$($총 스위치 수의 절반$)$

홀수일 때,
짝수와 똑같이 진행하다가 마지막 3개가 남는다면,

그 중 연달아 있는 두 개 누르고 불이 안켜지면 남은 하나가 답

켜지면, 방금 누른 것중에 하나랑 더 전에 눌렀던 거를 같이 누르면 확인 가능 -> 제곱의 절반의 반올림

n = int(input())
if n == 1:
    print(0)
else:
    print((n*n)//2+(n%2))

N=1일 때, 스위치가 하나라면 눌러보지 않아도 전구가 해당 스위치와 연결되어 있다는 사실을 알 수 있다.