[백준 1034] 램프

www.acmicpc.net/problem/1034

1034번: 램프

from collections import defaultdict

N,M = map(int,input().split())
lamp = []

for _ in range(N):
    lamp.append(input())

K = int(input())
d = {}

for i in lamp:
    if d.get(i):
        d[i][0]+=1
    else:
        #존재 안하면 "01" : [총 개수, 0의 수 ]
        cnt = i.count("0")
        d[i] = [1,cnt]

result = []
for i in d.values():
    result.append(i)

result.sort(reverse=True)
answer = 0
for i in range(len(result)):
    light_num,zero = result[i]

    if K < zero:
        continue
    else:
        if (K - zero)%2 == 0:
            # print("light_num,zero : ",light_num,zero)
            answer = light_num
            break;
        else:
            continue
print(answer)

풀이

처음엔 DP인 것 같았다. 전에 했던 선택이 앞으로의 값에 영향을 주는 듯 보였다.

그래서 dp[i][j]는 i번째 시도에 j램프를 눌렀을 때 켜져있는 최대 행 수 라고 생각하고 점화식을 짜보려 했으나 어떤 규칙도 찾지 못했다.

 

그러던 중 어떤 규칙을 발견했다.

바로 K를 생각 안 했을 때 전체가 켜질수 있는 행의 수는 이미 정해져 있었다.

 

010

101

001

100

 

이렇게 되어있다면 K가 어떤 수라도 최대 켜질 수 있는 수는 1이다.

왜냐면 겹치는게 하나도 없기 때문이다.

 

010

010

110

110

110

 

이거는 최대로 켜질 수 있는 수는 3이다.

 

여기서 한 번 더 생각해서 

만약 K가 1,3,5,7,9라면 답이 3이 나올 것이고 2,4,6,8 이라면 답이 2가 나올 것이다.

이것은 '0'의 숫자에 영향을 받는다.

 

0->1로 만들어야 하기 때문에 스위치는 최소 0의 개수번은 눌러줘야 한다.

 

그래서 일단 겹치는 문자열들의 개수를 세고, 그 문자열의 '0'의 수를 파악했다.

그리고 가장 겹치는게 많은 문자열부터 반복문을 돌렸다.

 

반복문 안에서 K가 0의 수를 넘을때와 0의 수를 안 넘을때를 구분한다.

 

안 넘었을 경우에는 그 다음으로 겹치는게 많은 문자열로 넘어갔고,

 

넘었을 경우에는 K-(0의 수) 가 짝수인 경우와 홀수인 경우를 구분했다.

 

짝수일 경우에는 즉시 답이 되고, 홀수일 경우엔 다시 다음으로 겹치는게 많은 문자열로 넘어갔다.

 

시간복잡도

램프들 배열을 for문에 돌리면서 0의 수를 체크한다.

이때 램프의 수는 N이고 0을 체크하는게 M만큼의 시간이 걸리기 때문에

시간복잡도는 O(NM)이다.