DP16 [python] 2916. 자와 각도기 문제 출처 2916. 자와 각도기 풀이 N, K = map(int, input().split()) degrees = list(map(int, input().split())) res = list(map(int, input().split())) possible = [0]*360 possible[0] = 1 q = [0] while q: degree = q.pop(0) for i in degrees: small, big = i-degree, i+degree if small = 360: big -= 360 if not possible[small]: possible[small] = 1 q.append(small) if not possible[big]: possible.. 2019. 8. 8. [python] 1904. 01타일 문제 출처 2904. 01타일 풀이 N = int(input()) if N == 1: print(1) else: a, b = 1, 2 for i in range(N-2): a, b = b, a+b print(b % 15746) 2019. 8. 8. [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] 1003. 피보나치 함수 문제 출처 1003. 피보나치 함수 풀이 피보나치를 재귀로 짰을때 0과 1이 리턴되는 횟수를 구하는 문제이다. 이 문제를 처음에는 재귀로 풀었는데 시간 복잡도 O(2^N)으로 시간 초과가 났다. 시간을 줄이기 위해 재귀가 아닌 for문을 이용해 이 전에 계산한 결과를 저장해 다음 결과를 도출하는 DP로 풀었더니 시간복잡도가 O(N)이 나왔다. 재귀 코드(시간초과) def fib(n): global zero, one if n == 0: zero += 1 return 0 elif n == 1: one += 1 return 1 else: return fib(n-1) + fib(n-2) tc = int(input()) for _ in range(tc): n = int(input()) zero, one = 0, .. 2019. 6. 30. 이전 1 2 3 4 다음
