[백준] CLASS 4 달성하기 1일차

이진규·2022년 7월 24일
1

백준(PYTHON)

목록 보기
57/115

1. 거짓말(★집합)

링크 : https://www.acmicpc.net/problem/1043

from sys import stdin
input = stdin.readline

n, m = map(int, input().split())
truth = set(map(int, input().split()[1:]))

party = []
for _ in range(m):
    party.append(set(map(int, input().split()[1:])))

liar = [1] * m # 모든 파티에서 거짓말 할 수 있다고 일단 가정
for _ in range(m): # 이 첫번째 반복문이 없다면 후반부에 교집합이 발생한 부분을 반영하지 못하고 정답으로 넘어갈 수 있어서 모든 경우를 반복문 돌려줘야함. (ex. 예제7)
    for idx, par in enumerate(party):
        if truth & par: # 만약 진실을 알고 있는 사람이 있다면
            truth = truth | par # 진실 리스트에 사람을 추가한다.
            liar[idx] = 0 # 진실을 말한다.

print(sum(liar))

2. RGB거리(DP)

링크 : https://www.acmicpc.net/problem/1149

from sys import stdin
input = stdin.readline

n = int(input())
dp = [ list(map(int, input().split())) for _ in range(n) ]

for i in range(1, n):
    dp[i][0] += min(dp[i-1][1], dp[i-1][2])
    dp[i][1] += min(dp[i-1][0], dp[i-1][2])
    dp[i][2] += min(dp[i-1][0], dp[i-1][1])

print(min(dp[n-1]))
profile
항상 궁금해하고 공부하고 기록하자.

0개의 댓글