https://www.acmicpc.net/problem/2156

 

2156번: 포도주 시식

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규

www.acmicpc.net

문제 해결을 위한 과정

이 문제 역시 전형적인 dp로 해결할 수 있는 문제였습니다. 계단 오르기 문제(https://www.acmicpc.net/problem/2579)와 거의 유사하였으나 계단 오르기 문제는 꼭 마지막을 밟아야 한다는 조건이 있었던 반면 이 문제의 경우는 마지막 포도주를 꼭 먹어야 한다는 조건이 존재하지 않습니다. 따라서 max 조건에서 data[i] + dp[i-2], data[i] + data[i-1] + dp[i-3]과 함께 dp[i-1] 조건 역시 비교해야 합니다. 따라서 이를 소스코드로 작성하면 다음과 같습니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = int(input())
data = [0] * 10001
dp = [0] * 10001
 
for i in  range(n):
  data[i] = int(input())
 
dp[0] = data[0]
dp[1] = data[0] + data[1]
dp[2] = max(data[0] + data[1], data[0] + data[2], data[1]+ data[2])
 
for i in range(3, n):
  dp[i] = max(data[i] + dp[i-2], data[i] + data[i-1] + dp[i-3], dp[i-1])
 
print(max(dp))
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 9251번: LCS(Python)  (0) 2022.01.29
백준 알고리즘 1904번: 01타일(Python)  (0) 2022.01.28
백준 알고리즘 1912번: 연속합(Python)  (0) 2022.01.25
백준 알고리즘 1149번: RGB거리(Python)  (0) 2022.01.24
백준 알고리즘 11053번: 가장 긴 증가하는 부분 수열(Python)  (0) 2022.01.20

https://www.acmicpc.net/problem/1912

 

1912번: 연속합

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 연속적으로 순자를 선택한 후 그 합이 최대가 되도록 하면 해결할 수 있는 dp 문제입니다. 따로 dp 리스트를 만들기보다 입력받은 리스트를 그대로 활용하면 보다 간단하게 해결할 수 있는 문제였습니다. 먼저 예시를 통해 알아봅시다.

 

0번째 인덱스까지의 최대의 합은 0번째 인덱스 그대로입니다.

10 -4 3 1 5 6 -35 12 21 -1

 

1번째 인덱스까지의 최대의 합은 1번째 인덱스 그대로가 아닌 0번째 + 1번째입니다.

10 6 3 1 5 6 -35 12 21 -1

 

2번째 인덱스까지의 최대의 합은 2번째 인덱스 그대로가 아닌 0번째 + 1번째 + 2번째입니다.

10  6 9 1 5 6 -35 12 21 -1

 

위와 같은 방식으로 6번째 인덱스 까지는 인덱스 그대로가 아닌 합으로 이루어집니다. 이는 아래의 그림과 같습니다.

10 6 9 10 15 21 -14 12 21 -1

 

다만, 7번째 인덱스까지의 최대의 합은 0번째부터 7번째까지의 합이 아닌 7번째 인덱스 그 자체입니다. 따라서 7번째 인덱스는 그대로 유지됩니다.

10 6 9 10 15 21 -14 12 21 -1

 

8번째 인덱스까지의 최대의 합은 8번째 그대로가 아닌 7번째 + 8번째입니다.

10 6 9 10 15 21 -14 12 33 -1

 

9번째 인덱스까지의 최대의 합은 9번째 그대로가 아닌 7번째 + 8번째 + 9번째입니다. 위의 표를 기반으로 점화식을 작성하면 다음과 같습니다.

 

data[i] = max(data[i], data[i-1] + data[i])

이를 소스코드로 표현하면 다음과 같습니다.

소스코드
1
2
3
4
5
6
7
n = int(input())
data = list(map(int, input().split()))
 
for i in range(1, n):
  data[i] = max(data[i], data[i] + data[i-1])
  
print(max(data))
 cs

 

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 1904번: 01타일(Python)  (0) 2022.01.28
백준 알고리즘 2156번: 포도주 시식(Python)  (0) 2022.01.25
백준 알고리즘 1149번: RGB거리(Python)  (0) 2022.01.24
백준 알고리즘 11053번: 가장 긴 증가하는 부분 수열(Python)  (0) 2022.01.20
백준 알고리즘 2579번: 계단 오르기(Python)  (0) 2022.01.19

https://www.acmicpc.net/problem/1149

 

1149번: RGB거리

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나

www.acmicpc.net

문제 해결을 위한 과정

이 문제 역시 전형적인 dp 즉 다이내믹 프로그래밍으로 해결할 수 있는 문제였습니다.

이해하기 쉽게 그림으로 그리면 다음과 같습니다. 간략하게 예시 1에 대해서 살펴봅시다.

먼저 3행 3열 이면서 int(1e9)으로 이루어진 이차원 리스트 dp는 다음과 같습니다.

 

그 후 0행에 예제의 정보들을 넣어주면 다음과 같습니다.

그 후 같은 열을 제외한 값을 더한 후 min값을 넣어주면 다음과 같습니다.

0행 1열에 대해서는 다음과 같습니다.

이러한 방식에 대해서 반복해나가면 쉽게 해결할 수 있습니다. 

소스코드 - python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n = int(input())
data = []
for _ in range(n):
  a, b, c = map(int, input().split())
  data.append((a, b, c))
 
dp = [[int(1e9)] * 3 for _ in range(n)]
a, b, c = data[0]
dp[0][0] = a; dp[0][1] = b; dp[0][2] = c
 
for i in range(n-1):
  for j in range(3):
    for k in range(3):
      if j == k:
        continue
      else:
        dp[i+1][k] = min(dp[i+1][k], dp[i][j]+data[i+1][k])
 
print(min(dp[n-1]))
 cs
소스코드 - c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
#define MAX 1001
using namespace std;
 
int main(void) {
  int n;
  scanf("%d", &n);
 
  int house[MAX][3];
  for(int i = 0; i < n; i++) {
    for (int j = 0; j < 3; j++) {
      scanf("%d", &house[i][j]);
    }
  }
 
  long long dp[MAX][3];
 
  fill(&dp[0][0], &dp[MAX-1][3], 1e9);
  dp[0][0] = house[0][0];
  dp[0][1] = house[0][1];
  dp[0][2] = house[0][2];
 
  for(int i = 0; i < n-1; i++) {
    for (int j = 0; j < 3; j++) {
      for (int k = 0; k < 3; k++) {
        if (j == k)
          continue;
        else
          dp[i+1][k] = min(dp[i+1][k], dp[i][j] + house[i+1][k]);
      }
    }
  }
 
  long long minValue = 1e9;
  for (int i = 0; i < 3; i++) {
    if(minValue > dp[n-1][i])
      minValue = dp[n-1][i];
  }
  printf("%lld", minValue);
  return 0;
}
 cs

위의 코드는 언뜻보면 O(n^3)인 것처럼 보이지만 사실상 두 번째, 세 번째 루프가 3까지 반복하므로 시간 복잡도가 O(n^3)이 아닌 것을 알 수 있습니다. 따라서 시간 초과 판정을 받지 않고 해결할 수 있습니다.

 

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 2156번: 포도주 시식(Python)  (0) 2022.01.25
백준 알고리즘 1912번: 연속합(Python)  (0) 2022.01.25
백준 알고리즘 11053번: 가장 긴 증가하는 부분 수열(Python)  (0) 2022.01.20
백준 알고리즘 2579번: 계단 오르기(Python)  (0) 2022.01.19
백준 알고리즘 1003번: 피보나치 함수(Python)  (0) 2022.01.19
 

https://www.acmicpc.net/problem/2579

 

2579번: 계단 오르기

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점

www.acmicpc.net

문제 해결을 위한 과정

이 문제를 해결하는데 있어서 가장 중요한 것은 마지막 계단을 밟아야 한다는 것이며 첫번째 계단을 밟지 않아도 된다는 것 입니다. 문제의 규칙에 따르면 다음과 같습니다.

  1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
  2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
  3. 마지막 도착 계단은 반드시 밟아야 한다.

먼저 계단이 한개일때 최대 점수는 다음과 같습니다.

첫 번째 계단이자 마지막 계단을 밟는 경우 -> 10점

 

계단이 두개일때 최대 점수는 다음과 같습니다.

첫 번째 계단과 마지막 계단을 밟는 경우 ->10 + 20점

 

계단이 세개일때 최대 점수는 다음과 같습니다.

두번째 계단과 마지막 계단을 밟는 경우 -> 20 + 15점

 

계단이 네개일때 최대 점수는 다음과 같습니다.

첫번째 계단과 두번째 계단 및 네번째 계단을 밟는 경우 -> 10 + 20 + 25점

 

다만 세번째 부터 다음과 같은 규칙이 적용되는것을 알 수 있습니다. (단, 마지막 계단이 n번째 일때)

최대의 점수 = max(n번째 계단 + n-2번째 까지의 최대 점수, n번째 계단 + n-1번째 계단 n-3번째 까지의 최대 점수)

이를 소스코드로 표현하면 다음과 같습니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = int(input())
data = [0] * 301
for i in range(n):
    data[i] = int(input())
 
 
dp = [0] * 301
dp[0] = data[0]
dp[1] = data[0] + data[1]
dp[2] = max(data[2] + data[1], data[2] + data[0])
for i in range(3, n+1):
  dp[i] = max(data[i] + data[i-1] + dp[i-3], data[i] + dp[i-2])
 
print(dp[n-1])
 
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 1149번: RGB거리(Python)  (0) 2022.01.24
백준 알고리즘 11053번: 가장 긴 증가하는 부분 수열(Python)  (0) 2022.01.20
백준 알고리즘 1003번: 피보나치 함수(Python)  (0) 2022.01.19
백준 알고리즘 7569번: 토마토(Python)  (0) 2022.01.15
백준 알고리즘 10026번: 적록색약(Python)  (0) 2022.01.15

https://www.acmicpc.net/problem/1003

 

1003번: 피보나치 함수

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 0을 호출하는 횟수, 1을 호출하는 횟수에 관한 것입니다. dp는 우선 n에 따른 결괏값을 나열한 뒤 규칙성을 파악하는 것이 가장 중요합니다. 따라서 n에 따른 규칙성을 파악해 보겠습니다. N의 값에 따른 0이 출력되는 횟수, 1이 출력되는 수를 표로 정리하면 다음과 같습니다.

4를 예시로 들어보면 다음의 그림과 같습니다.

위의 그림과 표에서 볼 수 있듯 fibonacci(4) 는 0을 2회 출력, 1을 3회 출력하는 것을 확인할 수 있다.

위의 표를 잘 살펴 보면 N >= 2일 때의 0, 1의 출력 횟수는 각각 N-1, N-2의 0, 1의 출력 횟수의 합인 것을 알 수 있다.

즉 이러한 규칙성을 가지고 문제를 해결하면 다음과 같다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
tc = int(input())
data = []
for i in range(tc):
  data.append(int(input()))
 
zeroCount = [1, 0]
oneCount = [0, 1]
 
for i in range(2, 41):
  zeroCount.append(zeroCount[i-1] + zeroCount[i-2])
  oneCount.append(oneCount[i-1] + oneCount[i-2])
 
for i in range(tc):
  print(zeroCount[data[i]], oneCount[data[i]])
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 11053번: 가장 긴 증가하는 부분 수열(Python)  (0) 2022.01.20
백준 알고리즘 2579번: 계단 오르기(Python)  (0) 2022.01.19
백준 알고리즘 7569번: 토마토(Python)  (0) 2022.01.15
백준 알고리즘 10026번: 적록색약(Python)  (0) 2022.01.15
백준 알고리즘 4963번: 섬의 개수(Python)  (0) 2022.01.15

https://www.acmicpc.net/problem/1010

 

1010번: 다리 놓기

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

www.acmicpc.net

문제 해결을 위한 과정

이 문제는 순서를 중요하게 생각하지 않는 '조합'의 방식으로 해결할 수 있는 문제였습니다. 동시에 팩토리얼 연산을 해야 하므로 Dynamic Programming의 방식 역시 문제 풀이의 한 요소였습니다.

팩토리얼을 우리가 흔히 아는 방식 즉 재귀적으로 구현하게 되면 한번 구한 연산을 지속적으로 반복하기 때문에 필요 없는 수많은 연산을 하게 되어 많은 컴퓨팅 리소스를 잡아먹게 됩니다. 또한 당연하게도 시간제한에 걸리게 됩니다. 따라서 이를 시간 내에 구현할 수 있게 하기 위해 피보나치수열 혹은 팩토리얼의 경우 탑다운 또는 보텀업 방식을 이용하여 해결합니다. 

문제에서 N <= M이라는 조건으로 생각해보면 결국 M개의 사이트 중에서 순서에 상관없이 N개를 뽑는 경우입니다. 가령 N이 2개이고 M이 3개일 시, 3개의 M 중에서 2개를 순서에 상관없이 뽑는 경우입니다. (예를 들면 AB, AC, BA, BC, CA, CB) 이를 염두에 두고 소스코드를 작성하면 다음과 같습니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
dp = [0] * 31
dp[0] = 1
dp[1] = 1
 
for i in range(2, 31):
  dp[i] = dp[i-1] * i
 
T = int(input())
for i in range(T):
  n, m = map(int, input().split())
  a = dp[m-n]
  b = dp[m]
  c = dp[n]
 
  print((b//a)//c)
 cs

위 소스코드에서 b//a는 mPn이고 이 결과를 c로 나눠야 mCn입니다.

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 10610번: 30(Python)  (0) 2022.01.03
백준 알고리즘 1026: 보물(Python)  (0) 2022.01.03
백준 알고리즘 1463번: 1로 만들기 (Python)  (0) 2021.12.27
백준 알고리즘 13549: 숨바꼭질 3(Python)  (0) 2021.02.25
백준 알고리즘 1504: 특정한 최단 경로(Python)  (0) 2021.02.23

+ Recent posts

티스토리툴바