백준-17273 카드 공장 (Small)

문제 링크

• 17273번: 카드 공장 (Small)

 

문제 요약

$N$장의 카드가 있고, 각 카드는 앞면과 뒷면에 숫자가 적혀 있다. $M$번의 쿼리가 주어지며, 각 쿼리는 threshold 값 $K$를 의미한다. 현재 보이는 면의 숫자가 $K$ 이하인 카드는 뒤집는다. 모든 쿼리를 처리한 후 보이는 숫자들의 합을 구하라.

제한

• 17273 (Small): $N, M \le 10{,}000$

---

Small 풀이: 브루트포스

가장 직관적인 방법은 매 쿼리마다 모든 카드를 순회하며 조건을 확인하는 것이다.

n, m, *a = map(int, open(0).read().split())
cards = []
d = n << 1
for i in range(0, d, 2):
    cards.append([a[i], a[i+1], 0])  # [앞면, 뒷면, 현재면(0 or 1)]

tot = sum(card[0] for card in cards)

for j in range(d, d + m):
    th = a[j]
    for k in range(n):
        cface = cards[k][2]
        if cards[k][cface] <= th:
            nface = 1 - cface
            tot += cards[k][nface] - cards[k][cface]
            cards[k][2] = nface

print(tot)

시간복잡도: $O(NM) = 10^8$

카드 정보를 저장하기 위해 불필요하게 추가적인 2차원 배열을 만들고 있으니 입력받은 그대로를 활용하는 코드로 만들어 보았다.

n,m,*a=map(int,open(0).read().split())
d=n<<1 #2배길이를 구해서 활용
c=[0]*d #앞면 뒷면 상태를 저장할 곳, 인덱스 계산을 줄이려고 그냥 길이를 2배로 설정.
t=sum(a[0:d:2]) #카드 앞면의 합. 최초 상태
for j in range(d,d+m): #m개의 쿼리 순회
	for k in range(0,d,2): #개의 원소 순회
		if a[k+c[k]]<=a[j]: #현재 면이 기준보다 작거나 같은가
			c[k]=1-c[k] #뒤집기
			t+=a[k+c[k]]-a[k+1-c[k]] #바뀌는 변화량만큼 초기 합계에 더해줌
print(t)