https://www.acmicpc.net/problem/15486이전에 퇴사 문제도 풀었었는데, 이번 퇴사 2번은 이렇게 풀면 안 된다...퇴사 문제는 N이 최대 15까지였지만, 이번 문제는 1,500,000이기 때문.. 따라서 이에 대해 고민을 해 보아야 한다.지금 생각할 수 있는 건... 아무래도 T, 즉 한 상담에 걸릴 수 있는 기간이 최대 50이기 때문에 크기가 50인 배열을 사용하여, 현재 시점 이전의 max값은 저장해두고, 이후의 값들은 배열에 저장하는 거다.. 대신 하루가 지날 때마다 값을 하나씩 땡겨와야 한다...import sysinput = sys.stdin.readlinen = int(input())end=0dp = [0 for _ in range(50)]for _ in range(..
https://www.acmicpc.net/problem/15988import sysinput=sys.stdin.readlinet = int(input())dp = [0 for _ in range(1000000)]dp[0],dp[1],dp[2] = 1,2,4for x in range(3,1000000): dp[x] = (dp[x-3]+dp[x-2]+dp[x-1])%1000000009for _ in range(t): print(dp[int(input())-1]) 전형적인 DP 문제로, 순서가 중요하다는 것을 유념하자.맨 마지막에 올 수 있는 숫자가 1,2,3이고, 그 앞을 이전에 저장해둔 개수로 넣으면 된다.
https://www.acmicpc.net/problem/1926 하나의 그림, 즉 하나로 연결된 객체들의 개수를 구하는 것DFS로 풀었다.import sysinput=sys.stdin.readlinesys.setrecursionlimit(10**6)n,m = map(int, input().split())graph =[]for _ in range(n): graph.append(list(map(int, input().split())))mv=[[-1,0],[0,-1],[1,0],[0,1]]picture=[]def dfs(y,x,idx): graph[y][x]=-1 picture[idx]+=1 for dy, dx in mv: ny,nx = dy+y, dx+x if 0
https://school.programmers.co.kr/learn/courses/30/lessons/132265from collections import defaultdictdef solution(topping): answer = 0 left = defaultdict(int) right = defaultdict(int) for t in topping: right[t]+=1 for x in topping: left[x]+=1 if right[x]==1: right.pop(x) else: right[x]-=1 if len(left)==len(right): answer+=1 return answer 왼쪽, 오른쪽..
https://www.acmicpc.net/problem/1244import sysinput = sys.stdin.readlinen = int(input()) #스위치 개수switch = list(map(int, input().split())) # 스위치 상태ppl = int(input())for _ in range(ppl): gen, x = map(int, input().split()) if gen==1: ## 남학생 i=x-1 while i 전형적인 구현 문제이다.
https://www.acmicpc.net/problem/1912import sysinput=sys.stdin.readlinen = int(input())dp = [0 for _ in range(n)]nums = list(map(int, input().split()))dp[0] = nums[0]for i in range(1,n): dp[i] = max(dp[i-1]+nums[i],nums[i])print(max(dp)) 일단 가장 먼저 생각할 수 있는 이중 for 문을 통한 시간복잡도 O(n^2)으로 풀 수 있는데, 그렇게 하면 시간초과가 난다...무조건 dp를 사용하여 O(n)의 시간복잡도로 풀어야 한다.
https://www.acmicpc.net/problem/18353몇 명을 뺐을 때 전투력이 내림차순으로 정렬되면서 최소 인원을 제외해야 한다=> 즉 내림차순이 되는 부분수열 중 가장 길이가 긴 것을 찾는 형태임근데 내 입장에서는 내 직전값이 뭔지만 알면 지금 걸 포함할 수 있는지 없는지 알 수 있음나부터 쭉 이전으로 돌아보면서 직전값이 될 것을 선택했을 때 내 길이가 가장 길어질수있는 것을 찾으면 됨글로 쓰니까 되게 헷갈리지만 구현은 어렵지 않다O(N^2)의 형태가 될것... like 버블정렬import sysinput=sys.stdin.readlinen = int(input())dp = [0 for _ in range(n+1)]# dp[0]은 직전에 아무것도 넣지 않았을 때 계산을 위해 넣음val =..
https://www.acmicpc.net/problem/2583import sysinput=sys.stdin.readlinesys.setrecursionlimit(10**6)m,n,k = map(int, input().split())board = [[0 for _ in range(n)] for _ in range(m)]for _ in range(k): x1,y1,x2,y2 = map(int, input().split()) for y in range(y1, y2): for x in range(x1,x2): board[y][x]=1#1: 칠해짐, 0: 미방문, -1: 방문mv = [[1,0],[0,1],[-1,0],[0,-1]]arr=[]def dfs(y,x,id..
https://www.acmicpc.net/problem/1520 - dp로 현재까지 가능한 경우의 수를 계산하면서 가면 됨- 내리막길로만 이동 가능하므로, 이전의 값이 더 큰 경우에만 현재 위치로 이동 가능하다.'''틀린 해답'''import sysinput = sys.stdin.readlinem,n = map(int, input().split())board = []for _ in range(m): board.append(list(map(int, input().split())))check = [[0 for _ in range(n)] for _ in range(m)]check[0][0] = 1for i in range(m): for j in range(n): if i0 and bo..
https://www.acmicpc.net/problem/11048DP로 이전에 이동할 수 있는 좌표 중 가장 큰 값을 가지고 간다 + 현재 칸에 할당된 사탕도 더하기!import sysinput = sys.stdin.readlinen,m = map(int, input().split())maze = []for _ in range(n): maze.append(list(map(int, input().split())))dp = [[0 for _ in range(m)] for _ in range(n)]dp[0][0] = maze[0][0]for y in range(n): for x in range(m): if y>0 and x>0 : dp[y][x] = max(dp[y][x], dp[y-..
