해결 과정 처음에는 모든 Edge를 다 돌며 탐색하도록 했더니 시간 초과가 났다. 연결되어 있는 Edge가 1개인 경우만 돌며 탐색해도 4%에서 시간초과가 났다. 다른 방법이 있겠구나 찾아보니 트리에서 지름을 구하는 방법이 있었다. 나의 풀이 from collections import deque V = int(input()) graph = [[] for _ in range(V+1)] for _ in range(V): infoList = list(map(int, input().split())) vertex = infoList[0] edges = infoList[1:-1] for a, b in zip(edges[0::2], edges[1::2]): graph[vertex].append((a, b)) def ..
해결 과정 set을 활용해서 풀 수 있었던 문제. 처음에는 한 번만 돌면 되는 줄 알았으나, 그게 아니었음. 계속 돌면서 겹치는 것이 있는지 확인해야 하는 과정이 필요했다. 추가로 여러 조건들을 코드에 잘 녹여내야 최종적으로 정답을 맞출 수 있었음. ex) warning의 개수가 0인지 체크하는 과정 등 나의 풀이 N, M = map(int, input().split()) warning = set(list(map(int, input().split()))[1:]) if len(warning) == 0: print(M) else: answer = 0 remain = [] isNew = True tmpNum = len(warning) for _ in range(M): participant = list(map(..
해결 과정 처음에는 1번째 원소 부터 작은 것을 선택해서 for 문 돌면서 최솟값을 선택하도록 했는데, 테스트케이스 5번에만 답이 안나오는 것을 발견했다. 다른 풀이가 있다는 뜻이기에 고민하다 DP임을 발견 다른 풀이를 참고했다. 직관적이다. 처음 부터 작은 원소를 선택하는 것이 아니라, 1번째를 제외한 RGB 각각에 대해 최솟값을 선택하도록 하면 된다. 나의 풀이 N = int(input()) cost = [] for _ in range(N): cost.append(list(map(int, input().split()))) dp = [[0, 0, 0] for _ in range(N)] dp[0] = cost[0] for i in range(1, N): dp[i][0] = min(dp[i-1][1], d..
해결 과정 역시 시간복잡도 고려 문제. O(n^2)을 줄이는 방법은 순차대로 1번씩만 돌 수 있는지 여부. 다른 풀이도 참고했다. 나의 풀이 N = int(input()) M = int(input()) S = input() pn = "IO" * N + "I" pnNum = len(pn) cur = 0 answer = 0 count = 0 while cur < M -1: if S[cur:cur+3] == "IOI": cur += 2 count += 1 if count == N: answer += 1 count -= 1 else: cur += 1 count = 0 print(answer) 첫 풀이 (50점) N = int(input()) M = int(input()) S = input() pn = "IO" ..
해결 과정 다이나믹 프로그래밍. 마지막에 인덱스 에러는 edge case를 살펴보면 된다. 해결 과정은 다른 풀이를 참고 했다. 여기서는 마지막 계단은 꼭 밟아야 하기 때문에 이를 기준으로 케이스를 분류한다. 그래서 else문 같은 식이 나온다. 나의 풀이 N = int(input()) score = [] for _ in range(N): score.append(int(input())) dp = [0] * (N+1) if N == 1: print(score[0]) elif N == 2: print(score[0] + score[1]) else: dp[0] = score[0] dp[1] = score[0] + score[1] dp[2] = max(score[0] + score[2], score[1] + s..
