[Python/BOJ] 백준 1034 램프_아이디어가 핵심

 

 

완탐인가 했는데 완탐은 맞다. 다만 아이디어를 곁들인...

 

대체 이런 아이디어는 어떻게 떠올리는지 궁금하다. 

 

 

 

 

---

 

 

 

1. 먼저 행별로 0의 개수를 구한다. 

 

2.  조건에 부합한 행을 찾는다.

 

2-1. 0의 개수가 k(변환 횟수)보다 크다면 k번을 다 뒤집어도 다 켜질수가 없으므로

첫번째 조건은 0의 개수가 k보다 작거나 같다. 

 

2-2.  그리고 두번 째 조건은 0의 개수가 짝수라면 k도 짝수 , 0의 개수가 홀수라면 k도 홀수여야한다. 

그 이유는 k 보다 작은 0들을 모두 1로 바꾼 다음 남은 k의 값이 짝수여야만 불이 켜진 상태를 유지할 수 있기 때문이다. 

 

만약 0이 짝수고 k도 짝수라면 k의 개수에서 0을 빼면 남는 값은 짝수이다. 

만약 0이 홀수고 k도 홀수라면 k의 개수에서 0을 빼면 남는 값은 짝수이다. 

 

남는 값이 짝수라면 불을 껐다가 킬 수있으므로 원상태로 돌아올 수 있다. 즉, 상관이 없다. 

 

3. 행들을 돌면서 나와 같은 행들의 개수를 센다. 

 

 

 

 

 

---

 

 

 

 

 

def solve() :
    answer = 0
    # 행을 돌면서 
    for i in mp :
    	# 0의 개수를 구한다. 
        zero_cnt = i.count(0)
        # 0의 개수가 k보다 작거나 같고 홀수면 홀수, 짝수면 짝수라면 
        if zero_cnt <= k and zero_cnt%2 == k%2 :
            cnt = 0
            # 행을 다시 돌면서 동일한 값의 행의 개수를 구한다. 
            for j in mp :
                if j == i : cnt+=1 
            # 최대값을 갱신한다. 
            answer = max(answer,cnt)
    return answer

if __name__=="__main__" :
    n,m = map(int,input().split())
    mp = [list(map(int,input())) for _ in range(n)]
    k = int(input())
    print(solve())

 

 

 

 

---

 

 

 

 

 

 

 

 

 

 

 

참고 블로그 : 

https://velog.io/@do0134/Python-1034-%EB%9E%A8%ED%94%84

[Python] 1034 램프

https://yhkim4504.tistory.com/11

백준 1034 번 : 램프 - 파이썬