취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 26005번 문제인 나뭇잎 학회이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/26005 

스위치가 3개 이상 있는 경우를 생각해보자. 이는 N=1을 제외한 모든 테스트케이스에 적용될 수 있다.

전구와 연결된 스위치의 위치를 찾기 위해 스위치를 두 개씩 눌러보면서 후보를 차근차근 줄여나가야 한다. 이 때, 누른 두개의 스위치로 전구에 불이 켜지지 않는다면 정답 후보 스위치는 둘이 감소하고, 불이 들어온다면 정답 후보 스위치는 정확히 둘이 됨을 관찰하자. 특히 후보 스위치가 정확히 세개 남았을 때, 아직 눌러본 적 없는 두 개의 스위치를 눌렀을 때 불이 들어오는 것이 후보의 수가 가장 적게 감소하는(-1) 경우가 됨에 유의하자.

후보 스위치가 둘이 되었다면 그중 하나의 스위치만이 눌리게끔 스위치를 누르면 어떤 스위치가 전구와 연결되었는지 판별할 수 있게 된다.

위의 과정을 이용해 문제를 해결하는 식을 세우자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	if (N == 1) cout << 0;
	else cout << (N * N - 1) / 2 + 1;
}