본문 바로가기

acmicpc.net

 (21)
15684 사다리 조작 Samsung Expert의 문제이다. 처음에는 조건에 맞추기 위해서는... 수직선에 연결된 수평선들이 모두 짝수개 여야 한다... 라고 가정하고 시작했더니 얄짤없이 틀려버렸다. 이래저래 다시 머리를 굴려보며 문제의 조건과 제한 시간들을 계산해보다 결국 브루트 포스로 해결했다. 단순히 모든 수평선에 대한 조합을 이용하여 새로 수평선들을 구성해 준 뒤, 해당 사다리에 대해 검사하면 된다. 수평선에 대해서 2차원 배열로 구성하는 것이 조금 더 빠를 것 같았지만, 그냥 해쉬 테이블을 이용해서 구성시켰다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626..
2365 숫자판 만들기 그 동안 Max flow에 해당하는 문제는 Edmonds-Karp 알고리즘을 통해서만 해결했었는데, 이번 문제는 해당 알고리즘으로는 시간초과가 발생한다. 그래서 조금 더 상위의 알고리즘을 공부할 기회가 되었다. Dinic 알고리즘을 이용하면 해당 문제를 시간 내에 해결이 가능하다. BFS로는 Source로 부터 Sink까지 이동할 수 있는 경로에 한해 Level을 구해주고, 해당 level을 이용한 Dfs로 max flow를 구할 수 있다. 사실 문제의 관건은 그래프의 구성이기도 하였다. 행의 합과 열의 합이 문제의 입력으로 주어지기 때문에 그래프의 구성에 있어서도 고민을 조금 했다. 1. Source로 부터 행의 합들에 대하여 생성한 노드들(Entrance)과 연결한다. 2. 이후 행의 노드는 해당 행..
5373 큐빙 제법 머리를 굴려서 해결한 문제이다. 가상의 큐브가 있을때, 상단의 왼쪽 뒷편을 (0,0,0)으로 기준을 잡자. 이후 x, y, z 축을 이용하여 각 큐브를 3차원 배열에 대입한다. 문제의 조건에서 앞면(Front), 뒷면(Back), 왼쪽면(Left), 오른쪽면(Right), 윗면(Up), 아랫면(Down)에 해당하는 면에 대한 접선과 그 중심 Cell의 좌표를 아래와 같이 미리 구해둔다. 12CENTERS = {'U': (1,1,0), 'D': (1,1,2), 'F': (1,2,1), 'B': (1,0,1), 'L': (0,1,1), 'R':(2,1,1)}DIRECTIONS = {'U': (0,0,-1), 'D': (0,0,1), 'F': (0,1,0), 'B': (0,-1,0), 'L': (-1,0..
3367 갤럭시 S9 공정개발 Samsung expert 문제이다. 단순한 DP로 접근하면 N^3으로 시간초과가 발생한다. 해당 문제로 고민하다가, 결국 구글링해보니 Knuth 최적화를 적용해야 N^2의 시간 복잡도를 가지게 되어 통과할 수 있다. 12345678910111213141516171819202122232425262728293031323334from itertools import accumulateINF = 999999999 def data_in(): return int( input()), list( map(int, input().split())) def solution( size, products) -> int : # initialize dp table & accumulate sum dp_table = [[0 for _ ..
2117 홈 방범 서비스 Samsung expert 문제이다. 123456789101112131415161718192021222324252627282930313233343536373839404142def data_in(): N, M = map( int, input().split()) return N, M, [ list( map( int, input().split())) for _ in range( N)] def get_house_location( size, city_map) -> list: result = [] for row in range( size): for col in range( size): if city_map[row][col] : result.append( (row, col)) return result def get_..
16236 아기 상어 해당 위치를 기준으로 BFS를 이용하여 거리를 구한다. 이후 동일한 거리 내 점들을 정렬시키면 자연스레 조건에 맞는 위치가 가장 앞에 있다. 이를 이용하여 문제를 해결한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869def data_in(): size = int( input()) return size, [ list( map( int, input().split())) for _ in range( size)] def get_shark_pos(): for row in range( size): for col in range( ..
16234 인구 이동 BFS를 이용하여 인접한 나라들을 구한다. 이후 해당 연합을 합쳐주는 방식으로 진행한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162def data_in(): N, L, R = map( int, input().split()) return N, L, R, [ list( map(int, input().split())) for _ in range(N)] def is_in( row, col): return 0
15686 치킨 배달 치킨 식당에 대한 조합문제이다. 특별한 조건없이 조합을 이용해 해결하면 되기에, itertools 라이브러리의 combination 함수를 이용하면 매우 간단하게 해결 가능하다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546from itertools import combinationsINF = 987654321 def data_in(): N, M = map( int, input().split()) return N, M, [ list( map( int, input().split())) for _ in range( N)] def get_building_pos(): houses, restaurants = [..

티스토리툴바