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/11053

 

11053번: 가장 긴 증가하는 부분 수열

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

문제 해결을 과정

이 문제의 경우 기존에 비슷한 문제를 포스팅 한게 있어서 그것으로 대체 하도록 하겠습니다.

https://bgspro.tistory.com/33?category=981927 

 

가장 긴 증가하는 부분 수열 - Longest Increasing Subsequence (Python)

개념 가장 긴 증가하는 부분 수열 다시 말하면 LIS라고도 하는 이것은 다이나믹 프로그래밍 기법 중에 하나입니다. 말 그대로 어떤 수열이 주어졌을 때 해당하는 수열에서 오름차순 혹은 내림차

bgspro.tistory.com

 

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

백준 알고리즘 1912번: 연속합(Python)  (0) 2022.01.25
백준 알고리즘 1149번: RGB거리(Python)  (0) 2022.01.24
백준 알고리즘 2579번: 계단 오르기(Python)  (0) 2022.01.19
백준 알고리즘 1003번: 피보나치 함수(Python)  (0) 2022.01.19
백준 알고리즘 7569번: 토마토(Python)  (0) 2022.01.15
 

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/7569

 

7569번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100,

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 3차원을 고려해야 한다는 점에서 조금 특이한 문제였습니다. 다만 3차원 리스트라는 점을 제외하면 이전에 풀었던 토마토 문제(https://www.acmicpc.net/problem/7576)와 비슷한 문제 이므로 어렵지 않게 해결할 수 있습니다. 

즉 상자의 위, 아래를 고려해야 하므로 dx, dy 뿐만 아니라 높이를 의미하는 dz 역시 존재해야 합니다. 따라서 for문을 6개로 구분하여 for i in range(6):으로 해결해야 합니다.

문제 해결을 위한 팁

3차원 리스트의 선언은 다음과 같이 선언할 수 있습니다.

graph = [[[0] * m for _ in range(n)]for _ in range(h)]

이렇게 하면 n행 m열의 그래프가 h만큼의 높이를 가지게 됩니다. 

접근하는 방법은 다음과 같습니다. 0번째 층의 1행 2열을 접근하려면 graph [0][1][2]로 접근할 수 있고

1번째 층의 2행 3열에 접근하려면 graph[1][2][3]으로 접근할 수 있습니다. 이 3차원 리스트에 지식을 가지고 접근하면 쉽게 해결할 수 있습니다.

소스코드
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
42
43
44
45
46
47
48
49
50
51
from collections import deque
 
def bfs(graph, tomato):
  count = 0
  while tomato:
    for _ in range(len(tomato)):
      x, y, z = tomato.popleft()
      for i in range(6):
        nx = x + dx[i]
        ny = y + dy[i]
        nz = z + dz[i]
        if nx < 0 or ny < 0 or nz < 0 or nx >= n or ny >= m or nz >= h:
          continue
        if graph[nz][nx][ny] == 0:
          graph[nz][nx][ny] = 1
          tomato.append((nx, ny, nz))
    count += 1
  return count
 
m, n, h = map(int, input().split())
graph = [[[0] * m for _ in range(n)] for _ in range(h)]
tomato = deque()
 
for k in range(h):
  for i in range(n):
    inputData = list(map(int, input().split()))
    for j in range(m):
      graph[k][i][j] = inputData[j]
      if graph[k][i][j] == 1:
        tomato.append((i, j, k))
 
dx = [-1, 1, 0, 0, 0, 0]
dy = [0, 0, -1, 1, 0, 0]
dz = [0, 0, 0, 0, -1, 1]
 
day = bfs(graph, tomato)
numOfZero = 0
 
for k in range(h):
  for i in range(n):
    for j in range(m):
      if graph[k][i][j] == 0: 
        numOfZero += 1
 
if numOfZero == 0:
  print(day-1)
else:
  print(-1)
 
      
 
 cs

 

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

백준 알고리즘 2579번: 계단 오르기(Python)  (0) 2022.01.19
백준 알고리즘 1003번: 피보나치 함수(Python)  (0) 2022.01.19
백준 알고리즘 10026번: 적록색약(Python)  (0) 2022.01.15
백준 알고리즘 4963번: 섬의 개수(Python)  (0) 2022.01.15
백준 알고리즘 18870번: 좌표 압축(Python)  (0) 2022.01.14

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

 

10026번: 적록색약

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 적록색약을 가진 분들과 적록색약이 아닌 분들이 보는 것이 다르다는 것을 이용한 문제입니다.

그것을 제외하고는 일반적인 bfs 문제와 같습니다. 예시를 들면 다음과 같습니다.

위의 그림이 있을 때 적록색약이 아닌 분들은 R, G, B로 3가지 구역, 적록색약인 분들은 RG, B로 2가지 구역으로 보는 것입니다. 따라서 이 점에 유의하며 bfs를 구현하면 됩니다.

문제 해결을 위한 팁

저의 경우는 그래프를 2개로 하여 기존에 입력받은 그래프를 복사하여 사용하였습니다. 이를 copy를 이용하였는데 copy의 경우 shallow copy, deep copy가 존재합니다. shallow copy의 경우 원본 혹은 복사본을 수정할 경우 기존의 그래프 역시 수정이 되므로 deep copy를 사용하여야 합니다. 따라서 import copy, 원본 = copy.deepcopy(복사본)를 사용합니다.

소스코드
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
from collections import deque
import copy
 
def bfs(graph, i, j):
  q = deque()
  q.append((i, j))
  target = graph[i][j]
  graph[i][j] = 'a'
  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if nx < 0 or ny < 0 or nx >= n or ny >= n:
        continue
      if graph[nx][ny] == target:
        graph[nx][ny] = 'a'
        q.append((nx, ny))
 
def bfs2(graph, i, j):
  q = deque()
  q.append((i, j))
  target = graph[i][j]
  graph[i][j] = 'a'
  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if nx < 0 or ny < 0 or nx >= n or ny >= n:
        continue
      if target == 'R' or target == 'G':
        if graph[nx][ny] == 'R' or graph[nx][ny] == 'G':
          graph[nx][ny] = 'a'
          q.append((nx, ny))
      else:
        if graph[nx][ny] == target:
          graph[nx][ny] = 'a'
          q.append((nx, ny))
      
        
 
n = int(input())
graph = [['a'] * n for _ in range(n)]
for i in range(n):
  inputData = list(input()) 
  for j in range(n):
    graph[i][j] = inputData[j]
 
graph2 = copy.deepcopy(graph)
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
count = 0
for i in range(n):
  for j in range(n):
    if graph[i][j] != 'a':
      bfs(graph, i, j)
      count += 1
 
print(count, end=" ")
 
count = 0
for i in range(n):
  for j in range(n):
    if graph2[i][j] != 'a':
      bfs2(graph2, i, j)
      count += 1
 
print(count)
 cs

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

백준 알고리즘 1003번: 피보나치 함수(Python)  (0) 2022.01.19
백준 알고리즘 7569번: 토마토(Python)  (0) 2022.01.15
백준 알고리즘 4963번: 섬의 개수(Python)  (0) 2022.01.15
백준 알고리즘 18870번: 좌표 압축(Python)  (0) 2022.01.14
백준 알고리즘 7576번: 토마토(Python)  (0) 2022.01.14

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

 

4963번: 섬의 개수

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 일반적인 상, 하, 좌, 우 네가지 방향을 탐색하는 bfs 문제에서 조금 벗어난 대각선까지 포함하는 8가지 방향을 탐색해야 하는 문제 입니다. 

일반적인 네가지 방향의 경우와 달리 여덟가지 방향을 그림으로 표현하면 다음과 같습니다.

따라서 dx, dy 리스트를 다음과 같이 만들고 for i in range(8)로 반복하면 됩니다.

 

dx = [-1, -1, 0, 1, 1, 1, 0, -1]

dy = [0, 1, 1, 1, 0, -1, -1, -1]

소스코드
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
from collections import deque
 
def bfs(graph, visited, i, j):
  q = deque()
  q.append((i, j))
  visited[i][j] = 1
  while q:
    x, y = q.popleft()
    for i in range(8):
      nx = x + dx[i]
      ny = y + dy[i]
      if nx < 0 or ny < 0 or nx >= n or ny >= m:
        continue
      if graph[nx][ny] == 1 and visited[nx][ny] == 0:
        visited[nx][ny] = 1
        q.append((nx, ny))
      
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]  
while True:
  m, n = map(int, input().split())
  if m == 0 and n == 0:
    break
  graph = []
  for _ in range(n):
    graph.append(list(map(int, input().split())))
  visited = [[0] * m for _ in range(n)]
 
  count = 0
  for i in range(n):
    for j in range(m):
      if graph[i][j] == 1 and visited[i][j] == 0:
        bfs(graph, visited, i, j) 
        count += 1
  print(count)
 cs

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

백준 알고리즘 7569번: 토마토(Python)  (0) 2022.01.15
백준 알고리즘 10026번: 적록색약(Python)  (0) 2022.01.15
백준 알고리즘 18870번: 좌표 압축(Python)  (0) 2022.01.14
백준 알고리즘 7576번: 토마토(Python)  (0) 2022.01.14
백준 알고리즘 18870번: 좌표 압축(Python)  (0) 2022.01.12

+ Recent posts

티스토리툴바