본문 바로가기

전체 글92

[python] 14501. 퇴사 문제 출처 14501. 퇴사 풀이 상담원은 매일 상담을 할 수도 있고 하지 않을수도 있다. 하지만 상담을 하게되면 상담하는 일 수 만큼 다음 상담을 할 수 없다. 만약 상담이 퇴사한 이후까지 이어진다면 해당 상담은 하지 않는다. 이 문제는 완전탐색을 할때 최악의 경우 매일 상담을 해야한다. 그래도 N의 범위가 15 이하이므로, 2^15(32768)번만 작업하면 되므로 완전탐색을 해도 무방하다. Brute Force N = int(input()) table =[list(map(int, input().split())) for _ in range(N)] max_ = 0 def func(day, pay): global max_ if day >= N: if day == N: tot = sum(pay) else: .. 2019. 7. 10.
[python] 14499. 주사위 굴리기 문제 출처 14499. 주사위 굴리기 풀이 주사위 배열을 모두 0으로 초기화 한다. 각 방향별로 굴렸을때 굴리기 전의 인덱스를 담은 배열을 만든다. 순서대로 명령을 실행하며 이동 한 후 지도를 벗어나는 명령은 건너뛴다. 다음 주사위의 값을 담은 배열을 생성하고 윗 면의 수를 출력한다. 이때 지도의 값이 0이면 주사위 바닥에 복사하고, 0이 아니면 지도에 주사위 바닥의 수를 복사한다. 주사위의 위치와 다음 주사위의 배열을 기존 변수에 덮어쓴다. N, M, y, x, K = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(N)] cmd = input().split() cube = [0] * 6 direction =.. 2019. 7. 8.
[python] 2636. 치즈 문제 출처 2636. 치즈 풀이 주어진 배열에서 가장 외각부터 안쪽으로 한 단계씩 들어가며 모두 없어질 때까지의 시간과 마지막에 남은 치즈의 갯수를 구하는 문제이다. 입력은 가로, 세로 최대 100이며 제한 시간은 1초 이므로 기본적인 BFS 탐색으로도 충분 하다. 치즈가 없어질때 까지의 시간 time과 시간별로 없어지는 치즈의 수인 cnt를 0으로 초기화 한다. 주어진 배열의 상하좌우에 0을 추가해 준다. 치즈가 존재하지 않는 (0, 0) 인덱스를 q에 추가해 준다. q에서 처음꺼를 pop해서 배열의 상하좌우를 탐색하며 아래 조건에 해당하는 인덱스만 q에 추가한다. 배열의 범위(0 = N+2: continue if arr[ny][nx] == 0: arr[ny][nx] = -1 q.append((ny, .. 2019. 7. 4.
[python] 7576. 토마토 문제 출처 7576. 토마토 풀이 주어진 배열에서 익은 토마토의 위치를 찾고, 그 위치부터 배열 전체의 가능한 부분을 BFS 탐색 하는 문제이다. 이 문제에서 최악의 경우 배열의 크기는 10^6으로 단순히 리스트 형식의 자료구조로 BFS 탐색을 하게되면 시간초과가 발생한다. 합격 코드는 단순 리스트구조와 heapq, deque로 해결한 풀이를 모두 작성했다. 단순 리스트(시간 초과) M, N = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(N)] q = [] for y in range(N): for x in range(M): if arr[y][x] == 1: q.append((0, y, x)) arr[y][.. 2019. 7. 1.

티스토리툴바