본문 바로가기

공부/알고리즘42

[알고리즘][백준] 2225번 합분해 - 파이썬(python) 풀이 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net import sys n, k = map(int, sys.stdin.readline().split()) dp = [[0] * (201) for _ in range(201)] dp[0][0] = 1 for i in range(0, n+1): for j in range(1, k+1): dp[i][j] = dp[i-1][j] + dp[i][j-1] print(dp[n][k] % 1000000000) # for i in range(1, 201): # dp[1][i] = i # dp[i][1] = 1 # for i in range(2.. 2024. 3. 10.
[알고리즘][백준] 1699번 제곱수의 합 - 파이썬(python) 풀이 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 나의 아이디어노트 import sys import math n = int(sys.stdin.readline()) d = [100000] * (n+1) d[1] = 1 d[2] = 2 d[3] = 3 if n d[i-j*j] + 1 : d[i] = d[i-j*j] + 1 print(d[n]) d[2] > d[1] + 1 (X) d[3] > d[2] + 1 (X.. 2024. 3. 9.
[알고리즘][백준] 1912번 연속합 - 파이썬(python) 풀이 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net # # sol 1 import sys # 정수 및 수열 n = int(sys.stdin.readline()) a = list(map(int, sys.stdin.readline().split())) # dp - n까지의 연속합 중 max d = [0] * n d[0] = a[0] # 현재값 VS 이전까지의 합 + 현재값 for i in range(1, n): d[i] = max(a[i], d[i-1] + a[.. 2024. 3. 8.
[알고리즘][백준] 14002번 가장 긴 증가하는 부분 수열 4 - 파이썬(python) 풀이 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 11053번 가장 긴 증가하는 부분 수열의 응용 문제로 부분 수열의 길이 출력에 부분 수열까지 출력하는 문제이다. 이미 앞 문제에서 수열 길이를 max(dp)로 출력하였고 dp에서 1~max(dp)인 순서대로 a 수열에서 뽑아오면 되는 문제이다 import sys n = int(sys.stdin.readline()).. 2024. 3. 8.

티스토리툴바