백준 온라인 저지, 그리디 / 3088번: 화분부수기 (파이썬 / 백준 골드문제)

문제

상근이는 K512 뒤쪽에 화분 N개를 놓았다. 태완이는 이 화분을 모두 부수어 버리려고 한다. 화분은 한 줄로 놓여져 있으며, 세 정수가 쓰여져 있다.

태완이가 화분 하나를 깼을 때, 그 화분에 쓰여있는 숫자와 오른쪽에 있는 임의의 화분에 쓰여있는 숫자가 하나라도 겹친다면 해당하는 화분은 깨진다. 이것은 연쇄적으로 일어난다. 따라서, 태완이는 화분 하나만 깨서 모든 화분을 깰 수 있다.

의외로 게으른 아이인 태완이는 되도록 적은 수의 화분을 직접 깨서 모든 화분을 깨지게 만들려고 한다. 이때, 태완이가 직접 깨야하는 화분의 최소 개수를 구하는 프로그램을 작성하시오.

위의 그림에서 2번 화분을 깬다면, 3번과 4번 화분은 숫자 2가 겹치기 때문에 화분이 깨지며, 숫자 9가 겹치기 때문에 화분 5가 깨지게 된다. 이제 남은 화분은 1번이기 때문에, 1번만 깨면 모든 화분을 깰 수 있다. 태완이는 화분 두 개를 직접 깨서 모든 화분을 깰 수 있다.

입력

첫째 줄에 화분의 개수 N이 주어진다. (1 ≤ N ≤ 300,000)

다음 N개 줄에는 각 화분에 쓰여 있는 숫자 세 개 A_i, B_i, C_i가 놓여져 있는 순서대로 주어진다. (1 ≤ A_i, B_i, C_i ≤ 1,000,000)

출력

첫째 줄에 태완이가 직접 깨야하는 화분 개수의 최솟값을 출력한다.

제한

예제 입력 1

3
1 2 3
2 3 4
4 5 6

예제 출력 1

1

예제 입력 2

5
3 4 1
2 5 6
7 2 8
2 1 9
11 10 9

예제 출력 2

2

힌트

W3sicHJvYmxlbV9pZCI6IjMwODgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ2NTRcdWJkODQgXHViZDgwXHVjMjE4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgSzUxMiBcdWI0YTRcdWNhYmRcdWM1ZDAgXHVkNjU0XHViZDg0IE5cdWFjMWNcdWI5N2MgXHViMTkzXHVjNTU4XHViMmU0LiBcdWQwZGNcdWM2NDRcdWM3NzRcdWIyOTQgXHVjNzc0IFx1ZDY1NFx1YmQ4NFx1Yzc0NCBcdWJhYThcdWI0NTAgXHViZDgwXHVjMjE4XHVjNWI0IFx1YmM4NFx1YjlhY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1ZDY1NFx1YmQ4NFx1Yzc0MCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1YjE5M1x1YzVlY1x1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YzEzOCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjNGYwXHVjNWVjXHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMGRjXHVjNjQ0XHVjNzc0XHVhYzAwIFx1ZDY1NFx1YmQ4NCBcdWQ1NThcdWIwOThcdWI5N2MgXHVhZTdjXHVjNzQ0IFx1YjU0YywgXHVhZGY4IFx1ZDY1NFx1YmQ4NFx1YzVkMCBcdWM0ZjBcdWM1ZWNcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHVjNjQwIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjNzg0XHVjNzU4XHVjNzU4IFx1ZDY1NFx1YmQ4NFx1YzVkMCBcdWM0ZjBcdWM1ZWNcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHVhYzAwIFx1ZDU1OFx1YjA5OFx1Yjc3Y1x1YjNjNCBcdWFjYjlcdWNlNWNcdWIyZTRcdWJhNzQgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1ZDY1NFx1YmQ4NFx1Yzc0MCBcdWFlNjhcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YWM4M1x1Yzc0MCBcdWM1ZjBcdWMxYzRcdWM4MDFcdWM3M2NcdWI4NWMgXHVjNzdjXHVjNWI0XHViMDljXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1ZDBkY1x1YzY0NFx1Yzc3NFx1YjI5NCBcdWQ2NTRcdWJkODQgXHVkNTU4XHViMDk4XHViOWNjIFx1YWU2OFx1YzExYyBcdWJhYThcdWI0ZTAgXHVkNjU0XHViZDg0XHVjNzQ0IFx1YWU3MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NThcdWM2NzhcdWI4NWMgXHVhYzhjXHVjNzNjXHViOTc4IFx1YzU0NFx1Yzc3NFx1Yzc3OCBcdWQwZGNcdWM2NDRcdWM3NzRcdWIyOTQgXHViNDE4XHViM2M0XHViODVkIFx1YzgwMVx1Yzc0MCBcdWMyMThcdWM3NTggXHVkNjU0XHViZDg0XHVjNzQ0IFx1YzljMVx1YzgxMSBcdWFlNjhcdWMxMWMgXHViYWE4XHViNGUwIFx1ZDY1NFx1YmQ4NFx1Yzc0NCBcdWFlNjhcdWM5YzBcdWFjOGMgXHViOWNjXHViNGU0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWQwZGNcdWM2NDRcdWM3NzRcdWFjMDAgXHVjOWMxXHVjODExIFx1YWU2OFx1YzU3Y1x1ZDU1OFx1YjI5NCBcdWQ2NTRcdWJkODRcdWM3NTggXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9hNzQyODhhMi04MTJlLTQyNjItOWMzOS0zNTMwYjU3MWVhOTBcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDI5NnB4OyBoZWlnaHQ6IDEyN3B4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHVhZGY4XHViOWJjXHVjNWQwXHVjMTFjIDJcdWJjODggXHVkNjU0XHViZDg0XHVjNzQ0IFx1YWU2Y1x1YjJlNFx1YmE3NCwgM1x1YmM4OFx1YWNmYyA0XHViYzg4IFx1ZDY1NFx1YmQ4NFx1Yzc0MCBcdWMyMmJcdWM3OTAgMlx1YWMwMCBcdWFjYjlcdWNlNThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1ZDY1NFx1YmQ4NFx1Yzc3NCBcdWFlNjhcdWM5YzBcdWJhNzAsIFx1YzIyYlx1Yzc5MCA5XHVhYzAwIFx1YWNiOVx1Y2U1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVkNjU0XHViZDg0IDVcdWFjMDAgXHVhZTY4XHVjOWMwXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVjNzc0XHVjODFjIFx1YjBhOFx1Yzc0MCBcdWQ2NTRcdWJkODRcdWM3NDAgMVx1YmM4OFx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIDFcdWJjODhcdWI5Y2MgXHVhZTY4XHViYTc0IFx1YmFhOFx1YjRlMCBcdWQ2NTRcdWJkODRcdWM3NDQgXHVhZTcwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDBkY1x1YzY0NFx1Yzc3NFx1YjI5NCBcdWQ2NTRcdWJkODQgXHViNDUwIFx1YWMxY1x1Yjk3YyBcdWM5YzFcdWM4MTEgXHVhZTY4XHVjMTFjIFx1YmFhOFx1YjRlMCBcdWQ2NTRcdWJkODRcdWM3NDQgXHVhZTcwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDY1NFx1YmQ4NFx1Yzc1OCBcdWFjMWNcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDMwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVkNjU0XHViZDg0XHVjNWQwIFx1YzRmMFx1YzVlYyBcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwIFx1YzEzOCBcdWFjMWMgQTxzdWI+aTxcL3N1Yj4sIEI8c3ViPmk8XC9zdWI+LCBDPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWIxOTNcdWM1ZWNcdWM4MzggXHVjNzg4XHViMjk0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgQTxzdWI+aTxcL3N1Yj4sIEI8c3ViPmk8XC9zdWI+LCBDPHN1Yj5pPFwvc3ViPiAmbGU7IDEsMDAwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDBkY1x1YzY0NFx1Yzc3NFx1YWMwMCBcdWM5YzFcdWM4MTEgXHVhZTY4XHVjNTdjXHVkNTU4XHViMjk0IFx1ZDY1NFx1YmQ4NCBcdWFjMWNcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMDg4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRVhBTSIsImRlc2NyaXB0aW9uIjoiPHA+TWFydGluIGlzIGEgYmVhc3RseSBraWQsIHdobyBsaWtlcyBkZXN0cm95aW5nIGhpcyBtb3RoZXImIzM5O3MgZmxvd2VyIHBvdHMuIEhpcyBtb3RoZXIgb3ducyBOIGZsb3dlciBwb3RzIHNldCB1cCBpbiBhIGxpbmUgYW5kIGVhY2ggcG90IGhhcyB0aHJlZSBpbnRlZ2VycyB3cml0dGVuIG9uIGl0LiBXaGVuIE1hcnRpbiBjcmFzaGVzIG9uZSBvZiB0aG9zZSBwb3RzLCBldmVyeSBwb3QgcmlnaHQgb2YgdGhhdCBwb3QgYW5kIHNoYXJlcyBhdCBsZWFzdCBvbiBudW1iZXIgd2l0aCBpdCBhbHNvIGZhbGxzLiBNb3Jlb3ZlciwgdGhpcyBydWxlIGlzIGFwcGxpZWQgcmVjdXJzaXZlbHksIHRodXMgY2FuIHJlc3VsdCBpbiBjcmFzaGluZyBvZiB3aG9sZSBsb3R0YSBwb3RzIGZyb20ganVzdCBvbmUgZGlyZWN0IHBvdCBjcmFzaCBmcm9tIE1hcnRpbi4gQmVhc3RseSBraWRzIGFyZSBrbm93biB0byBiZSBsYXp5IGFuZCBzbyBpcyBNYXJ0aW4sIGFuZCBoZSB3YW50cyB0byBrbm93IHRoZSBtaW5pbWFsIG51bWJlciBvZiBwb3RzIGhlIGhhcyB0byBjcmFzaCBkaXJlY3RseSBzbyB0aGF0IGFsbCBwb3RzIGVuZCB1cCBkZXN0cm95ZWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvYTc0Mjg4YTItODEyZS00MjYyLTljMzktMzUzMGI1NzFlYTkwXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAyOTZweDsgaGVpZ2h0OiAxMjdweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+T24gdGhlIHBpY3R1cmUgYWJvdmUgdGhlIHNlY29uZCBzYW1wbGUgaXMgc2hvd24uIElmIERvbWFnb2ogY3Jhc2hlcyBwb3QgMiwgaXQgd2lsbCBhbHNvIGNyYXNoIHBvdCAzIGFuZCBwb3QgNCBiZWNhdXNlIG9mIG51bWJlciAyIGFuZCBhZGRpdGlvbmFseSBwb3QgNSBiZWNhdXNlIG9mIG51bWJlciA5IChmb3VuZCBvbiBwb3QgNCkuIEhlIG5lZWRzIHRvIGNyYXNoIHBvdCAxLCB3aGljaCB3aWxsIGNhdXNlIHRoZSBjcmFzaGluZyBvZiBwb3QgMy4gVGhpcyBhbW91bnRzIHRvIHR3byBkaXJlY3QgY3Jhc2hlcyBmcm9tIE1hcnRpbiBhbmQgaXMgdGhlIHNvbHV0aW9uIHRvIHRoZSBzYW1wbGUuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5GaXJzdCBsaW5lIGNvbnRhaW5zIG9uZSBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMzAwIDAwMCkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIHRocmVlIGludGVnZXImbmJzcDtBPHN1Yj5pPFwvc3ViPiwgQjxzdWI+aTxcL3N1Yj4sIEM8c3ViPmk8XC9zdWI+ICgxICZsZTsmbmJzcDtBPHN1Yj5pPFwvc3ViPiwgQjxzdWI+aTxcL3N1Yj4sIEM8c3ViPmk8XC9zdWI+ICZsZTsgMSAwMDAgMDAwKSwgdGhyZWUgbnVtYmVycyB3cml0dGVuIG9uIHRoZSBpLXRoIHBvdCBmcm9tIHRoZSBsZWZ0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkluIHRoZSBmaXJzdCBhbmQgb25seSBsaW5lIHdyaXRlIHRoZSBtaW5pbWFsIG51bWJlciBvZiBwb3RzIE1hcnRpbiBoYXMgdG8gY3Jhc2ggaGltc2VsZiB0byBjcmFzaCBhbGwgdGhlIHBvdHMuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

접근 방법

- 가장 왼쪽부터 순서대로 화분을 깨며 해당하는 숫자를 인덱스를 통해 dp에 1을 저장한다.
- 만약 화분을 깼을 때 이미 깬 화분의 숫자를 포함하고 있다면 그 화분은 숫자를 더하지 않는다.
- 만약 화분을 깼을 때 숫자가 없다면 dp에 해당 값들을 모두 저장하고 카운트를 추가한다.
- 모든 화분을 탐색한 뒤, 카운트를 출력한다.

코드

# https://www.acmicpc.net/problem/3088
# 접근방법
# 가장 왼쪽부터 순서대로 화분을 깨며 해당하는 숫자를 인덱스를 통해 dp에 1을 저장한다.
# 만약 화분을 깼을 때 이미 깬 화분의 숫자를 포함하고 있다면 그 화분은 숫자를 더하지 않는다.
# 만약 화분을 깼을 때 숫자가 없다면 dp에 해당 값들을 모두 저장하고 카운트를 추가한다.
# 모든 화분을 탐색한 뒤, 카운트를 출력한다.
import sys
input = sys.stdin.readline
n = int(input())
pot = [list(map(int, input().split())) for _ in range(n)]
count = 0
dp = [0 for _ in range(10**6 + 1)]
for a, b, c in pot:
    if not dp[a] and not dp[b] and not dp[c]:
        count += 1
    dp[a], dp[b], dp[c] = 1, 1, 1
print(count)