Hanbit the Developer

www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net import sys input = sys.stdin.readline def setJumpCounts(maxIndex): global jumpCounts lastIndex = 1 i = 2 while lastIndex < maxIndex: rep = (i+1)//2 jumpCounts.append(jumpCounts[i-1]+rep) lastIndex = jumpCou..

www.acmicpc.net/problem/2206 import sys input = sys.stdin.readline dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def bfs(): global stepMap todo = [(0, 0, 0)] while todo: curPos = todo.pop(0) if curPos[1] == N-1 and curPos[2] == M-1: return stepMap[curPos[0]][curPos[1]][curPos[2]] for i in range(4): curX, curY = curPos[1] + dx[i], curPos[2] + dy[i] if 0

www.acmicpc.net/problem/1654 import sys input = sys.stdin.readline def getLanCountAfterCut(lans, cutBy): lanCountAfterCut = 0 for lan in lans: lanCountAfterCut += lan//cutBy return lanCountAfterCut K, N = map(int, input().split()) lans = [int(input()) for _ in range(K)] left, right = 1, max(lans) while left

import sys input = sys.stdin.readline N = int(input()) nums = list(map(int, input().split())) dp = [0]*N for i in range(N): maxDp = 0 for j in range(i): if nums[j] < nums[i]: maxDp = max(maxDp, dp[j]) dp[i] = maxDp+1 print(max(dp)) 우선 일반적인 풀이이다. i에 대한 for문의 각각 수행하는 것은 다음과 같다. 0~i-1 인덱스에서, nums가 nums[i]보다 작으면서 dp가 최대인 값(maxDp)를 찾고, 현재 dp에 maxDp+1을 넣어주는 것이다. 즉, 예시와 같은 경우 dp의 값은, [1, 2, 1, 3, 2, 4]..

www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net N = int(input()) dp = [[0]*10 for _ in range(N+1)] for i in range(1, 10): dp[1][i] = 1 for i in range(2, N+1): dp[i][0] = dp[i-1][1] for j in range(1, 9): dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] dp[i][9] = dp[i-1][8] print(sum(dp[N]) % 1000000000) bfs 같은 것을 통해 직접 구현하는 것은 터무니없이 느리다. 따라서 DP를 이용한다. ..

www.acmicpc.net/problem/4673 def d(n): RET = n for c in str(n): RET += int(c) return RET isSelfNumberList = [True]*10001 for i in range(10000): curD = d(i) if curD

www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net import sys input = sys.stdin.readline def getIsPrimeNumberList(N): isPrimeNumberList = [True]*(N+1) isPrimeNumberList[1] = False for i in range(2, int(N**(1/2))+1): if isPrimeNumberList[i]: j = 2 while i*j

www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net import sys input = sys.stdin.readline N = int(input()) nums = [0]*10001 for _ in range(N): nums[int(input())] += 1 for i in range(10001): for j in range(nums[i]): sys.stdout.write(str(i)+"\n") 메모리 제한이 8MB인데, 10,000,000개의 숫자를 저장할 수는 없다.(이를 위해..

www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net import sys input = sys.stdin.readline T = int(input()) for _ in range(T): x1, y1, r1, x2, y2, r2 = map(int, input().split()) distance = ((x1-x2)**2+(y1-y2)**2)**(1/2) if x1 == x2 and y1 == y2: if r1 == r2: print(-1) else: print(0) else: if distance < r1+r2: big..

www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net import sys import heapq input = sys.stdin.readline def bfs(start): global minWeights minWeights[start] = 0 heap = [] heapq.heappush(heap, (0, start)) while heap: curWeight, curNode = heapq.heappop(heap) for adjacentN..