1034번: 램프
첫째 줄에 N과 M이 주어진다. N은 행의 개수이고, M은 열의 개수이다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져
www.acmicpc.net
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)이다.
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
[백준 12851] 숨바꼭질 2 파이썬 (0) | 2021.05.13 |
---|---|
[백준 18405] 경쟁적 전염 (0) | 2021.05.12 |
[백준 1027] 고층 건물 (0) | 2021.05.12 |
[백준 1004] 어린왕자 (0) | 2021.05.12 |
[백준 15954] 인형들 (0) | 2021.05.11 |
댓글