https://www.acmicpc.net/problem/11444단순 DP만을 사용해서는 시간초과로 인해 풀 수 없다. DP와 다른 방법을 같이 사용해야 한다.아래는 시간초과되는 코드이다.import sysinput= sys.stdin.readlinen = int(input())arr = [0,1]for _ in range(n-1): arr[0],arr[1] = arr[1], (arr[0]+arr[1])%1000000007if n==1: print(0)else : print(arr[1]) https://velog.io/@kjy2134/%EB%B0%B1%EC%A4%80-11444-%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%88%98-%ED%8C%8C%EC%9D%B4%E..
https://www.acmicpc.net/problem/12891import sysinput = sys.stdin.readlines, p = map(int, input().split()) #문자열 길이, 부분문자열 길이arr = list(input().rstrip())check = list(map(int, input().split()))chars = {'A':0, 'C':1, 'G':2, 'T':3}ans=0for x in arr[:p]: check[chars[x]]-=1 if max(check)
https://www.acmicpc.net/problem/1655시간초과 시 PyPy3 쓰세요import heapqsmaller = [] # 중간값 이하의 값들 -> - 붙여서 저장bigger = [] # 중간값 초과의 값들def insert(num): if not smaller or num len(bigger)+1: heapq.heappush(bigger, -heapq.heappop(smaller)) elif len(bigger) > len(smaller): heapq.heappush(smaller, -heapq.heappop(bigger)) def get_median(): return -smaller[0] # 작은 값들 중 가장 큰 값n = int(inp..
https://www.acmicpc.net/problem/2493O(n^2)의 시간 복잡도로 이중 for문을 사용하면 시간초과가 되므로, 다른 방법을 사용해야 한다.# 시간복잡도 초과import sysinput = sys.stdin.readlinen = int(input())height = list(map(int, input().split()))ans = [0 for _ in range(n)]for i in range(n-1, -1, -1): for j in range(i-1, -1, -1): if height[i] 모노토닉 스택을 사용한 답변https://popsapple.tistory.com/86 모노토닉 스택 / 백준 2493 탑https://www.acmicpc.net/probl..
https://www.acmicpc.net/problem/10825 `sort()`와 `lambda`의 `key`를 사용하여, 주어진 조건의 순서대로 정렬이 가능하다.기본적으로 정렬은 ascending, 즉 오름차순이 기본값이기 때문에 내림차순으로 정렬하고 싶다면 lambda 사용 시 `-`를 붙여서 진행하면 된다.import sysinput = sys.stdin.readlinen = int(input())# 국어 감소, 영어 증가, 수학 감소, 이름 증가arr = []for _ in range(n): name, kor, eng, math= input().split() arr.append([int(kor), int(eng), int(math), name])arr.sort(key=lambda x..
https://www.acmicpc.net/problem/2644import sysinput = sys.stdin.readlinen = int(input())a,b = map(int, input().split())m = int(input())adj = [[] for _ in range(n+1)]for _ in range(m): x, y = map(int, input().split()) adj[x].append(y) adj[y].append(x)visited = [False for _ in range(n+1)]visited[a]=Trueans=-1def dfs(now, l, visited): if now==b: global ans ans = l ..
https://www.acmicpc.net/problem/1904 DP 문제로, https://www.acmicpc.net/problem/11726위의 문제와 로직이 동일하다! 현재 가능한 가짓수에서, 마지막 칸들은 00이거나 1 두 가지이다.따라서 마지막 두 칸을 00이라고 고정하면, 두 칸 전의 가짓수만을 고려하면 된다.마찬가지로 마지막 한 칸을 1으로 고정하면, 한 칸 전의 가짓수만을 고려하면 된다.두 가지 상황을 더했을 때, 현재 칸에서 가능한 가짓수들을 구할 수 있다. 이 것을 반복하면 되는데, 해당 문제는 메모리 제한이 있으므로 한칸 전, 두 칸 전 상황의 가짓수만을 저장하는 길이가 2인 배열을 사용하여 DP를 수행하면 된다. 또한 문제의 조건에서 볼 수 있듯이, 15746으로 나눈 나머지를 ..
https://www.acmicpc.net/problem/15651 중복되는 숫자도 가능하다는게, 이전 숫자와 관계없이 1~N까지 뽑을 수 있다는 것이다!!따라서 수열의 길이만 고려해주면 된다.다른 N과 M 문제들보다 쉬운 것 같다.import sysinput = sys.stdin.readlinen,m = map(int, input().split())# 1~n 자연수 중 m개 고른 수열, 같은 수 여러번 가능# 순서는 사전 순으로 증가arr = []def dfs(len): if len == m: print(*arr) else: for x in range(1, n+1): arr.append(x) dfs(len+1) if ar..
https://www.acmicpc.net/problem/11054 왼쪽으로 오른쪽으로 가면서, 현재 지점까지 가장 긴 증가 수열의 길이를 갱신해가며 dp 방식으로 풀면 된다.똑같이 오른쪽에서 왼쪽으로 가면서, 감소 수열의 길이를 갱신하며 풀어 그 둘을 합치고 1을 뺀 값이 가장 큰 수를 출력한다.import sysinput = sys.stdin.readlinen = int(input())up = [1 for _ in range(n)] # ~ i번째까지 가장 긴 증가 수열 길이down = [1 for _ in range(n)] # i ~ 끝까지 가장 긴 감소 수열 길이arr = list(map(int, input().split()))## 증가하는 부분수열 최대 길이for i in range(n): ..
https://www.acmicpc.net/problem/1946import sysinput = sys.stdin.readlinet = int(input())ans = [0]*tfor idx in range(t): n = int(input()) arr = [0 for _ in range(n+1)] # 서류 -> 면접 등수 for i in range(1, n+1): a,b = map(int, input().split()) arr[a]=b cnt =1 min_speak = arr[1] # 서류 1등 무조건 채용 -> 최소 면접 등수 for i in range(2, n+1): if arr[i]
