본문 바로가기

반응형

코딩

(89)
[Python] 백준 2225 합분해 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 코드 작성 n, k = map(int, input().split()) dp = [[0]*201 for _ in range(201)] for i in range(201): dp[1][i] = 1 for i in range(2, 201): dp[i][1] = i for j in range(2, 201): dp[i][j] = dp[i-1][j] + dp[i][j-1] print(dp[k][n] % 1000000000) 코드 풀이 #1 초기값 k = 1일 때, 즉 1자리수 일 때 N은 그 자신의 수만 될 수 있으므로 1이 된다. ..
[Python] 백준 1476 날짜 계산 1476번: 날짜 계산 (acmicpc.net) 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 코드 작성 a,b,c = map(int, input().split()) cnt = 0 while True: if a == 0 and b == 0 and c ==0: break if a == 0: a = 15 if b == 0: b = 28 if c == 0: c = 19 a -= 1 b -= 1 c -= 1 cnt += 1 print(cnt)
[Python] 백준 14002 가장 긴 증가하는 부분 수열4 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 코드 작성 n = int(input()) k = list(map(int, input().split())) dp = [1] * n for i in range(n): for j in range(i): if k[i] > k[j]: dp[i] = max(dp[i], dp[j] +1) print(max(dp)) Max = m..
[Python] 백준 2156 포도주 시식 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 코드 작성 n = int(input()) dp = [0] * 10001 w = [0] * 10001 for i in range(1, n+1): w[i] = int(input()) dp[1] = w[1] dp[2] = w[1] + w[2] for i in range(3, n+1): dp[i] = max(dp[i-1], dp[i-2] + w[i], dp[i-3] + w[i] + w[i-1]) print..
[Python] 백준 1932 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 코드 작성 n = int(input()) dp = [list(map(int, input().split())) for _ in range(n)] for i in range(1, n): for j in range(i+1): #i의 인덱스가 0부터 시작하므로 i+1번 해야함 if j == 0: dp[i][j] += dp[i-1][j] elif j == i: dp[i][j] += dp[i-1][j-1] else: dp[i][j] += max(dp[i-1][j-1], dp[i-..
[Python] 백준 2004 조합 0의 개수 코드 작성 def cnt2(n): two = 0 while n != 0: n = n//2 two += n return two def cnt5(n): five = 0 while n != 0: n = n//5 five += n return five n, m = map(int, input().split()) print(min(cnt2(n)-cnt2(n-m)-cnt2(m),cnt5(n)-cnt5(n-m)-cnt5(m))) 코드 풀이 #1. 콤비네이션 nCr = n! / { (n-r)! * r ! } 식을 활용하여 (1) n의 2배수 - n-m의 2배수 - m의 2배수 (2) n의 5배수 - n-m의 5배수 - m의 5배수 (1)식과 (2)식의 최소값을 구하면 된다. #2. 시간초과된 틀린코드 콤비네이션을 활용하..
[Python] 백준 1699 RGB거리 1149번: RGB거리 (acmicpc.net) 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 코드 작성 1 n = int(input()) rgb = [list(map(int, input().split())) for _ in range(n)] dp = [[0]*3 for _ in range(n+1)] for i in range(1,n+1): #2번째 수부터 n까지 dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + rgb[i-1][0] dp[i][1] = min(d..
[Python] 백준 1309 동물원 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 코드 작성 n = int(input()) dp = [[0]*3 for _ in range(n+1)] dp[0] = [1,1,1] for i in range(1, n): dp[i][0] = (dp[i-1][1] + dp[i-1][2]) % 9901 dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % 9901 dp[i][2] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) % 9901 print(sum(dp[n-1])%9901) 코드 풀이 #1. 점화식 dp[n][0] : 첫 번째 칸에 채워..

반응형