Hanbit the Developer

https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net import sys input = sys.stdin.readline def setDp(start): todo = [start] dp[start] = (0, 0) while todo: cur = todo.pop(0) if cur == 1: break if cur % 3 == 0 and dp[cur//3][0] > dp[cur][0] + 1: dp[cur//3] = (dp[cur][0] + 1, cur) todo.append(cur//3) if cur % 2 == 0 and dp[cur//2][0] > d..

https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net import sys import bisect input = sys.stdin.readline sys.setrecursionlimit(1000000) if __name__ == '__main__': N = int(input()) nums = list(map(int, input().split())) stack = [] stackLength = 0 # stack에서의 인덱..

https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net import sys import bisect input = sys.stdin.readline if __name__ == '__main__': N = int(input()) nums = list(map(int, input().split())) stack = [] for n in nums: minBiggerIndex = bisect.bisect_left(stack, n) if minBiggerInde..

https://www.acmicpc.net/problem/11049 import sys input = sys.stdin.readline if __name__ == '__main__': N = int(input()) nums = list(map(int, input().split())) for _ in range(N-1): _, c = map(int, input().split()) nums.append(c) # DP dp = [[0]*N for _ in range(N)] for d in range(N): for i in range(N - d): j = i + d if i == j: continue dp[i][j] = float('inf') for k in range(i, j): dp[i][j] = min(d..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net import sys sys.setrecursionlimit(300000) input = sys.stdin.readline def search(node): stack.append(node) visitInfo[node] = curSearchStart next = nums[node] nextVisitInfo = visitInfo[next] # 이번 탐색 때 방문한 경우 if nextVisitInfo == c..

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net import sys import copy input = sys.stdin.readline dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] def getCyclePositions(): airCleanerTopX = -1 airCleanerBottomX = -1 for i in range(R): if fineDusts[i][0] == -1: airCleanerTopX = i ai..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net import sys import itertools input = sys.stdin.readline dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] def getMinChickenDistance(): minChickenDistance = float('inf') # 치킨집 위치 & 치킨집 -> 집까지 거리 저장 chickenPositions = [] for i..

https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net import sys import itertools input = sys.stdin.readline if __name__ == '__main__': N, M = map(int, input().split()) nums = map(int, input().split()) for cur in sorted(list(set(itertools.permutations(nums, M)))): print(*cur)..

https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net import sys import itertools input = sys.stdin.readline if __name__ == '__main__': N, M = map(int, input().split()) nums = sorted(set(input().split()), key=lambda x: int(x)) for cur in itertools.combinations_with_replaceme..

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net import sys import heapq input = sys.stdin.readline def getPossibleItemCount(start): dp = [float('inf')]*(n+1) dp[start] = 0 todo = [(0, start)] while todo: curDist, curNode = heapq.heappop(todo) if curDist > dp[curNode]: conti..