본문 바로가기
728x90

알고리즘/[python] 백준 BOJ328

[Python] 백준 13398 연속합 2 https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 해결 리스트안에서 i번째에서 j번째의 합의 최댓값을 구하는 문제 BUT 중간에 하나의 수를 뺄 수 있다. n번째 까지 연속해서 왔을 때 최댓값은 n-1번째까지 수에 영향을 받으므로 dp를 이용하면 좋겠다는 것을 알 수 있다. 이는 처음부터 n 번째 수까지 나열했을 때 n까지 연속해서 오는동안 하나의 수도 안 뺀 최댓값을 dp[n][0], 중간에 하나 뺐으면 dp[n][1]으로 정의한다. 중간에 .. 2022. 12. 28.
[python] 백준 2133 타일 채우기 https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 문제 해결 $ 3 \times N$ 행렬에서 N이 홀수일 경우는 타일을 다 채울 수 없다. N이 짝수인 것은 명백하고 타일을 채우는 방법은 2X2, 2X4 .... 무척 다양하다. 하지만 다양해도 확실한 것은 짝수로 끝난다는 것이다. 이전 dp와 관련없이 만들어지는 타일 채우는 가지수는 +2가 있다. 따라서 다음과 같이 코드를 짤 수 있다. CODE import sys input = sys.stdin.readline n = int(input()) dp = [0 for i in range(31)] dp[2] .. 2022. 12. 27.
[python] 백준 9456 스티커 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제 해결 dp로 문제를 해결 해야할 것 같음 dp[0][n]을 n번째 열에는 스티커를 떼지 않고 얻을수 있는 점수 최대 값을 표현하고 dp[1][n]을 n번째 열에 1행 스티커를 땔 때 얻을 수 있는 점수 최댓값을 표현 dp[2][n]을 n번째 열에 2행 스티커를 땔 때 얻을 수 있는 점수 최댓값을 표현한다고 하고 코드를 짜면 쉽게 짤 수 있다. code import sys input.. 2022. 12. 27.
[python] 백준 17404 RGB거리2 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 해결 R, G, B 3 가지 선택지가 있으므로 dp를 사용할 때 dp[n][0], dp[n][1], dp[n][2] 를 사용해야 할 것 같다. 비욜 cost 리스트를 만들면 dp[n][0] = cost[n][0] + min(dp[n][1], dp[n][2]) 를 사용하면 바로 전에 같은 색을 칠하지 않고 최솟값을 구할 수 있다. 그런데 문제점! 1번 집의 색과 N.. 2022. 12. 26.
728x90