흰 스타렉스에서 내가 내리지

별다른 해법이 떠오르지 않아 처음부터 브루트포스로 접근했다. 그런데 시간초과가 났다. 아래는 시간초과가 난 코드이다. from itertools import combinations n = int(input()) data = list(map(int, input().split())) arr = [] for i in range(1, n+1): for c in combinations(data, i): _sum = sum(c) arr.append(_sum) i = 1 while True: if i not in arr: break i += 1 print(i) 여기서 쓸데없이 시간을 지체했던 부분은, 마지막 while 문에, if i not in arr: 를 실행할때마다 O(n)의 시간복잡도를 가진다는 것. 코드를 ..

다이나믹 프로그래밍과 BFS를 결합해서 풀어야 하는 문제다 dp배열에 전부 INF로 채우고, 재할당한 요소에 대해서 BFS를 진행하면 된다. 문제를 보면, -1을 뺄 수 있다 했는데, n=1000일때, 1001에서 1000이 되는 경우가 최솟값이 될수 있기 때문에, 배열의 크기를 1000으로 할게 아니라 1001로 해줘야 한다. 물론 1002에서 -1을 해주는 과정을 두번 해서 1000이 되는 케이스도 있을 수 있겠다. 일단 베열의 크기를 n+1 해주니까 정답을 맞추긴 했다. from collections import deque import sys input = sys.stdin.readline INF = int(1e9) n = int(input()) q = deque() dp = [[INF]*(n+2)..

다이나믹 프로그래밍을 이용하는 문제. 여기서 중요한 것은, 수가 굉장히 커진다는 것인데, a+b+c = d 일때, 모든 k에 대하여 {(a%k) + (b%k) + (c%k)} % k = d % k 가 성립한다. dp = [[0] for _ in range(100001)] dp[1] = [1, (1, 0, 0)] dp[2] = [1, (0, 1, 0)] dp[3] = [3, (1, 1, 1)] for i in range(4, 100001): a = dp[i-3][1][0] + dp[i-3][1][1] b = dp[i-2][1][0] + dp[i-2][1][2] c = dp[i-1][1][1] + dp[i-1][1][2] dp[i] = [a%1000000009 + b%1000000009 + c%1000000..

알아둬야 할 스킬이 두가지가 있었다. M과 N으로 나누어 떨어지는 어떤 수를 구하고자 할 때, for i in range(M*N): if i%M==0 and i%N==0: ... 을 할게 아니라, for i in range(0, M*N, M): if i%N==0:... 이렇게 하면 연산량을 크게 줄일수 있다는 것 그리고 가장 중요한 스킬 내가 원하는 결과 x f(x) 1 1 2 2 3 3 4 4 5 5 6 1 7 2 f(x) = x%5 를 하면 f(5)=0이 된다. x f(x) = x%5 1 1 2 2 3 3 4 4 5 0 6 1 7 2 x 대신 x-1을 함수에 넣고, 리턴 된 값을 1 더해주면 내가 원하는 결과를 얻을 수 있다. x x-1 (x-1)%5 (x-1)%5 + 1 1 0 0 1 2 1 1 2..

16926번 배열돌리기1 이랑 문제는 같지만, R의 범위가 아주 크다. 배열을 돌리면 처음상태로 돌아오는 지점이 있을 것이기 때문에, 나머지 연산을 통해 연산 횟수를 줄여주면 된다. 처음엔 deepcopy를 이용해서 구현을 했는데, 2차원 배열을 deepcopy하는것은 시간이 오래걸리는 작업이기 때문에 시간초과가 발생했다. # 시간초과가 발생했던 코드 import copy import sys input = sys.stdin.readline n, m, k = map(int, input().split()) arr = [] for _ in range(n): arr.append(list(map(int, input().split()))) def f(arr, k): start = 0 end_row = n-1 end..

최대 사이즈만큼 미리 배열을 생성한다. 반복문안에 방문한 점을 표시하기 위해 arr[next]=cnt+1 문을 추가했다. 이미 방문한 점에는 더 짧은 경로로 도달할 수 있는데, 굳이 큐에 추가할 필요가 없기 때문이다. 이렇게 방문한 점을 표시하지 않으면 큐의 길이가 기하급수적으로 늘어나 메모리 초과가 발생한다. from collections import deque n, k = map(int, input().split()) SIZE = 100001 arr = [0] * SIZE arr[n] = -1 def f(): # n==k if n==k: return 0, [] # k < n if k < n: return n-k, [i for i in range(n, k-1, -1)] q = deque() q.appe..

전형적인 DFS 문제. DFS 감을 잊지 않기 위해서, 다음에 한번 더 풀어보라고 포스트한다 N, M = map(int, input().split()) graph = [[] for _ in range(N)] for _ in range(M): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a) def dfs(graph, v, arr, visited): if len(arr)==5: return True for w in graph[v]: if w not in visited: ret = dfs(graph, w, arr+[w], visited+[w]) if ret: return True return False def f(): for i i..

dp[1] = 1 dp[2] = 2 dp[3] = 4 dp[4]: dp[1]에 3이 더해진 경우 dp[2]에 2가 더해진 경우 dp[3]에 1이 더해진 경우 따라서 dp[4] = dp[1] + dp[2] + dp[3] 이를 일반화 하면, dp[n] = dp[n-3] + dp[n-2] + dp[n-1] (if n ≥ 4) dp = [0] * (1000001) dp[1] = 1 dp[2] = 2 dp[3] = 4 for _ in range(int(input())): n = int(input()) if n

알고리즘 예를 들어 입력 배열로 4 5 1 3 2 이 들어왔다고 하자 ● 뒤에서부터, arr[i-1] < arr[i] 가 되는 i를 찾는다. i 는 3이 된다. ● x를 i-1이라 하고, y를 i라고 하자. 그러면 x는 2, y는 3이다 ● 뒤에서부터, arr[x] 보다 큰 값이 있으면, arr[x]와 swap하고, break한다. 그러면 배열은 4 5 2 3 1 이 된다. ● y 이후의 배열에 대하여 정렬을 한다. 즉, arr = arr[:y] + sorted(arr[y:]) ● 그러면 배열은 4 5 2 1 3 이 된다. 이것이 입력배열의 다음 순열이 된다. N = int(input()) arr = list(map(int, input().split())) def f(arr): for i in range..

이보다 쌩노가다 문제는 또 없을 것 같다. 저번에 직각삼각형 찾는 문제도 이런식으로 경우의수를 전부 다 기입한 후 푸는 문제였다. 배열에서 도형 관련된 문제는 이런 식으로 접근해야 할 가능성이 높아보인다 import sys input = sys.stdin.readline n, m = map(int, input().split()) arr = [] for _ in range(n): arr.append(list(map(int, input().split()))) dx = [None for _ in range(20)] dy = [None for _ in range(20)] dx[1] = [0, 0, 0, 0] dy[1] = [0, 1, 2, 3] dx[2] = [0, 1, 2, 3] dy[2] = [0, 0, 0..