본문 바로가기

분류 전체보기

 (44)
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 = [..
15685 드래곤 커브 점들을 기준으로 이차원 배열을 생성한다.해당 커브는 다음 세대로 넘어갈 때, 현재까지의 진행경로를 뒤집은 것을 추가한 것과 같다. 이를 이용해 브루트 포스로 접근하면 해결가능하다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475DIRS = [(0, 1), (-1, 0), (0, -1), (1, 0)]RU, RD, LD, LU = (-1,0), (0,0), (0,-1), (-1,-1)BORDERS, SIZE = [ RU, RD, LD, LU], 100boxes = None class Box : def _..
15683 감시 CCTV의 종류별로 가능한 방향들을 미리 설정해두고,브루트 포스로 간단하게 접근하면 해결가능하다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869from copy import deepcopy U, R, D, L = (-1,0), (0,1), (1,0), (0,-1)CCTV_DIRS = { 1: [[U],[R],[D],[L]], 2: [[L, R], [U, D]], 3: [[U, R], [R, D], [D, L], [L, U]], 4: [[U, R, D], [R, D, L], [D, L, U], [L, U, R]], 5: [..
14891 톱니바퀴 브루트 포스로 간단하게 접근하면 해결 가능하다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758CLOCKWISE, COUNTER_CLOCKWISE = 1, -1LEFT, RIGHT, N, S = -1, 1, '0', '1' def data_in(): return [ input() for _ in range(4)] def rotate( gear, direction): if direction == CLOCKWISE: temp = gear[-1] gear = temp + gear[:-1] elif direction == COUNTER_CLOCKWISE: temp = ..

티스토리툴바