BOJ 1034 - 램프

문제 : https://www.acmicpc.net/problem/1034

램프에 $K$번의 조작을 다 하고 나서 최종적으로 몇 개의 행의 불이 완전히 켜져있다고 생각해보자. 불이 완전히 켜져있는 행들은 초기에 서로 켜져있는 불의 상태가 완전히 같았어야한다. 왜냐하면 램프에 가해지는 조작은 열 단위로 가해지기 때문이다. 

위 사실을 알고나면, 문제를 이렇게 생각할 수 있다. $K$번의 조작을 해서 어떤 행의 불을 완전히 켤 수 있는가?
만약에 켤 수 있다면 그 행과 똑같이 생긴 행의 수를 답으로 고려해 볼 수 있고, 최종 답은 그러한 행의 수 중 최대가 된다.

이제 $K$번의 조작을 해서 어떤 행의 불을 완전히 켤 수 있는지를 알 수 있으면 되는데, 이는 처음에 꺼져있는 열의 수보다 $K$가 크거나 같을 때 홀짝만 잘 따지면 알 수 있다.

댓글

댓글 쓰기

이 블로그의 인기 게시물

BOJ 11478 - 서로 다른 부분 문자열의 개수

길이 $N$인 문자열 $S$의 서로 다른 부분 문자열의 개수를 세는 문제이다. 방법 1) Suffix Array + LCP $O(NlgN)$에 해결할 수 있다. 다른 곳에서 많이 볼 수 있는 풀이이다. 방법 2) 트라이 $O(N^2)$에 해결할 수 있다. 트라이에 $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 모두 넣으면 최종적으로 트라이에 존재하는 노드의 수 - 1(루트 제외)이 답이 된다. 방법 3) 해싱 $O(N^2lgN)$에 해결할 수 있다. $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 해싱하면서 유니크한 해싱값들의 수를 세면 된다. 코드 (트라이) :  http://ideone.com/bugbDy 코드 (해싱) :  http://ideone.com/hkjw5n
계속 읽기

파이썬 재귀 최대깊이 지정 sys.setrecursionlimit( limit )

https://docs.python.org/2/library/sys.html#sys.setrecursionlimit https://www.acmicpc.net/problem/1012 파이썬 써본지 얼마 안되서 DFS를 구현하는 문제를 풀었는데 알고리즘상에 문제가 없어보이는데 자꾸 오답이 나왔다. 무슨 문젠가 몇시간 동안 고민했는데 이유는 재귀깊이 한계치가 작아서였다. import sys sys.setrecursionlimit(10**6) 을 추가해줬더니 정답처리 됐다. import sys sys.setrecursionlimit( 10 * * 6 ) bat = [] dx = [ 0 , 1 , 0 , - 1 ] dy = [ 1 , 0 , - 1 , 0 ] M = N = K = 0 def dfs ( x , y ): bat[x][y] = 0 for k in range ( 4 ): i = x + dx[k] j = y + dy[k] if (i >= M or i < 0 or j >= N or j < 0 ): continue if (bat[i][j] == 1 ): dfs(i,j) return for t in range ( input ()): (M,N,K) = map ( int , raw_input ().split()) cnt = 0 bat = [[ 0 for j in range (N + 1 )] for i in range (M + 1 )] for i in range (K): (a,b) = map ( int , raw_input ().split()) bat[a][b] = 1 for i in range (M): for j in range (N): if
계속 읽기