HTD

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를 이용한다. ..

Windows 운영체제에서 파일의 대소문자가 달라도 같은 파일로 인식하므로, 직접 건드린다한들 소용이 없다. 파일명의 대소문자를 바꾸기 위해선 다음 명령어를 입력해야한다. git mv user.ts User.ts

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개의 숫자를 저장할 수는 없다.(이를 위해..

이 경우는, 깃허브가 파일명의 대소문자를 무시하는 옵션이 들어가서 발생한 것이다. git config core.ignorecase false 위의 명령어를 입력해주면 해결이 된다.

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..

nykim.work/15

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..