본문 바로가기

Problem Solving/BOJ60

[Two Pointer] python 1806 부분합 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net # 2023.02.04 import sys input = sys.stdin.readline n, s = map(int, input().split()) # 수열의 길이, 합 S이상이 되는 것 중 가장 짧은 것의 길이 a = list(map(int, input().split())) # 수열 left, right = 0, 0 answer=10**9 tmp=0 while True: if t.. 2023. 2. 4.
[문자열] python 20437 문자열 게임2 https://www.acmicpc.net/problem/20437 20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net # 2023.02.03 import sys input = sys.stdin.readline from collections import defaultdict t = int(input()) for _ in range(t): w = input().rstrip() k = int(input()) dic = defaultdict(list) for i in range(len(w)): # 문자열의 index.. 2023. 2. 3.
[DP] python 1309 동물원 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net # 2023.02.03 import sys input = sys.stdin.readline n = int(input()) answer=0 dp=[[0]*(n+1) for _ in range(3)] # 경우의 수를 저장 dp[0][1]=1 # 모두 선택하지 않는 경우 dp[1][1]=1 # 1행을 선택하는 경우 dp[2][1]=1 # 2행을 선택하는 경우 for i in range(2,n+1): #col을 +1씩 이동 # 현재 아무것도 선택하지 않았다면 그 전에는 (아무것도 선택하지 않음, 1행 선택, 2행 선택)->3가지 경우 모.. 2023. 2. 3.
[DP] python 12852 1로 만들기2 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net # 2023.01.30 import sys input = sys.stdin.readline n = int(input()) dp=[[0]*(2) for _ in range(n+1)] #연산을 하는 횟수의 최솟값 dp[1][0]=0 # 연산횟수 dp[1][1]=[1] # 연산순서 # n~1 dp table탐색 for i in range(2, n+1): dp[i][0]=dp[i-1][0]+1 # 연산횟수 dp[i][1]=dp[i-1][1]+[i] # 연산순서 if i%3==0 and dp[i//3][0]+1.. 2023. 2. 1.

티스토리툴바