그냥 코딩하는 사람의 블로그

문제 설명

문제

0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾아내어 그 길이를 출력하는 프로그램을 작성하라.

예를 들어 수열 1, 2, 2, 4, 4, 5, 7, 7, 2 의 경우에는 1 ≤ 2 ≤ 2 ≤ 4 ≤ 4 ≤ 5 ≤ 7 ≤ 7 이 가장 긴 구간이 되므로 그 길이 8을 출력한다. 수열 4, 1, 3, 3, 2, 2, 9, 2, 3 의 경우에는 3 ≥ 3 ≥ 2 ≥ 2 가 가장 긴 구간이 되므로 그 길이 4를 출력한다. 또 1, 5, 3, 6, 4, 7, 1, 3, 2, 9, 5 의 경우에는 연속해서 커지거나 작아지는 수열의 길이가 3 이상인 경우가 없으므로 2를 출력하여야 한다.

입력

첫째 줄에는 수열의 길이 N이 주어지고, 둘째 줄에는 N개의 숫자가 빈칸을 사이에 두고 주어진다. N은 1 이상 100,000 이하의 정수이다.

출력

첫째 줄에 가장 긴 길이를 출력한다.

풀이 과정

1. DP 테이블을 2개 구성한다 (증가, 감소)
   • up_dp, down_dp는 모두 기본값을 1로 구성한다(자기 자신만으로 구성된 수열의 길이:1)
   • seq[i] <= seq[i-1]인 경우 down_dp[i] = down_dp[i-1] + 1
   • seq[i] >= seq[i-1]인 경우 up_dp[i] = up_dp[i-1] + 1
2. 테이블을 모두 채웠으면 down_dp의 최댓값, up_dp의 최댓값중 큰 값을 리턴하면 된다.

소스 코드

import sys

input = sys.stdin.readline

n = int(input().rstrip())
sequence = list(map(int, input().rstrip().split()))

down_dp = [1] * n
up_dp = [1] * n

for i in range(1, n):
    if sequence[i-1] <= sequence[i]:
        up_dp[i] = up_dp[i-1] + 1
    if sequence[i-1] >= sequence[i]:
        down_dp[i] = down_dp[i-1] + 1

print(max(max(up_dp), max(down_dp)))

문제 설명

문제

혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서 문제를 만들려 한다.

int fibonacci(int n) { // 호출
  if (n < 2) {
    return n;
  } return
  fibonacci(n-2) + fibonacci(n-1);
}

위와 같이 코딩하였을 때 fibonacci(n)를 입력했을 때에 fibonacci 함수가 호출되는 횟수를 계산해보자.

입력

fibonacci 함수에 인자로 입력할 n이 주어진다. (0 ≤ n ≤ 50)

출력

fibonacci 함수가 호출된 횟수를 출력한다.

출력값이 매우 커질 수 있으므로 정답을 1,000,000,007 로 나눈 나머지를 출력한다.

풀이 과정

1. 아래에서부터 바텀-업 방식으로 진행
   • fibonacci(0)일때는 1번 호출하므로 dp[0] = 1
   • fibonacci(1)일때는 1번 호출하므로 dp[1] = 1
2. fibonacci(n >= 2) 일때는, fibonacci(n-1)을 호출하므로 fibonacci(n-1)번, fibonacci(n-2)를 호출하므로 fibonacci(n-2)번, 그리고 자기 자신까지 +1해주면 된다.
   • 즉, dp[i] = dp[i-1] + dp[i-2] + 1
3. 마지막으로 dp[n]을 1000000007로 나눈 나머지 값을 출력하면 된다.

소스 코드

import sys

n = int(sys.stdin.readline().rstrip())
dp = [0] * (n+1)
if n <= 1:
    print(1)
else:
    dp[0] = 1
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2] + 1

    print(dp[n] % 1000000007)

문제 설명

문제

춘향이는 편의점 카운터에서 일한다.

손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.

예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.

입력

첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.

출력

거스름돈 동전의 최소 개수를 출력한다. 만약 거슬러 줄 수 없으면 -1을 출력한다.

풀이 과정

1. i원이 되기 위해서는 i-2원에서 2원짜리를 주던가, i-5원에서 5원짜리를 주던가 두가지 경우밖에 없다.
2. 따라서 점화식을 dp[i] = min(dp[i-2]+1, dp[i-5]+1)로 세우면 된다.
3. 도달 불가능한 금액이 있을수 있으므로 초기값을 INF로 두고, dp[n]이 INF라면 -1을 출력하면 된다.

소스 코드

import sys

n = int(sys.stdin.readline().rstrip())
INF = int(10e9)
dp = [INF] * (n+1)
dp[0] = 0

for i in range(1, n+1):
    if i-2 >= 0:
        dp[i] = min(dp[i], dp[i-2]+1)
    if i-5 >= 0:
        dp[i] = min(dp[i], dp[i-5]+1)


if dp[n] == INF:
    print(-1)
else:
    print(dp[n])

문제 설명

문제

n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다.

입력

첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 m+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다.

출력

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

둘째 줄에는 그러한 최소 비용을 갖는 경로에 포함되어있는 도시의 개수를 출력한다. 출발 도시와 도착 도시도 포함한다.

셋째 줄에는 최소 비용을 갖는 경로를 방문하는 도시 순서대로 출력한다.

풀이 과정

1. Dijkstra 알고리즘 및 최소 히프 사용해서 시간 단축
2. 현재 시점에서 거리가 가장 짧은 노드 선택해서(최소 히프 사용) 연결된 노드들의 최단 경로 갱신
   • 최단 경로가 갱신된 경우 최소 히프에 등록
3. 과정을 반복하다 보면 .. 히프에 하나의 노드로 가는데 거리가 여러개가 나올 수 있음. [거리, 노드]라고 할때 [4, 9], [7, 9]
   • 따라서, 처음에 히프에서 빼줄 때, 현재 거리와 비교하는 과정 필요, ==> 이과정을 생략하면 시간 초과 나옴.
4. 최단 경로도 알아야 하므로, parent 배열에 자신을 방문하기 이전 노드들의 정보를 저장함.
   • 1->2 라고 할때, parent[2] = 1

소스 코드

import sys
import heapq

input = sys.stdin.readline
n = int(input().rstrip())
m = int(input().rstrip())
INT_MAX = int(10e9)

graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().rstrip().split())
    graph[a].append([b, c])

start, end = map(int, input().rstrip().split())
distance = [INT_MAX] * (n+1)
parent = [i for i in range(n+1)]
distance[start] = 0
candidate = [[0, start]]
while candidate:
    dist, node = heapq.heappop(candidate)
    if dist > distance[node]:
        # 갱신된 경우에는 넘겨줌
        continue
    for next_node, cost in graph[node]:
        if dist + cost < distance[next_node]:
            distance[next_node] = dist + cost
            parent[next_node] = node
            heapq.heappush(candidate, [distance[next_node], next_node])

print(distance[end])
answer = []
temp = end
while parent[temp] != temp:
    answer.append(temp)
    temp = parent[temp]
answer.append(start)
print(len(answer))
answer.reverse()
print(" ".join(list(map(str, answer))))

문제 설명

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 1,000,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

풀이 과정

1. n에 도달하기 위해서는 n-1에서 1 더하거나, n-2에서 2 더하거나, n-3에서 3 더하는 방법밖에 없음.
2. 따라서 dp를 dp[n] = dp[n-1] + dp[n-2] + dp[n-3]으로 해주면 된다.
3. 이 때, 그냥 해주면 수가 너무 커지게 되서 시간 초과가 나옴.
   • 매 순간 더해주는 값과 결과에 % 100000009를 해주어야 함.

소스 코드

import sys

input = sys.stdin.readline
n = int(input().rstrip())

dp = [0] * 1000001
a = 1
b = 2
c = 4
d = 0
for j in range(4, 1000001):
    d = (a + b + c) % 1000000009
    a = b % 1000000009
    b = c % 1000000009
    c = d % 1000000009
    dp[j] = d

for i in range(n):
    tc = int(input().rstrip())
    if tc == 1:
        print(1)
    elif tc == 2:
        print(2)
    elif tc == 3:
        print(4)
    else:
        print(dp[tc]) 

문제 설명

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

풀이 과정

1. 현재 칸에 도달하기 위해서는 이전 타일에서 1x2 타일을 붙이거나
2. 2칸 이전의 타일에서 2 x 1 타일을 2개 붙이거나 2x2 타일을 1개 붙이는 경우이다.
3. 따라서, dp[n] = dp[n-1] + dp[n-2] * 2가 된다.
   • x2 해주는 이유는, 2가지 케이스로 도달 가능하므로 경우의 수는 2배가 된다.
4. 점화식을 통해 아래에서부터 위로 테이블을 채워주면 된다.

소스 코드

import sys

input = sys.stdin.readline
n = int(input().rstrip())
if n == 1:
    print(1)
    sys.exit(0)

dp = [0] * (n+1)
dp[1] = 1
dp[2] = 3
for i in range(3, n+1):
    dp[i] = dp[i-1] + (dp[i-2] * 2)

print(dp[n] % 10007)

문제 설명

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

풀이과정

★ 다른 알고리즘 문제에서도 많이 쓰임!!

1. DP[n]을 n번째 인덱스까지의 합으로 설정한다.
   • DP[n] = array[0]~[n]까지의 합
2. 따라서 a 인덱스~b 인덱스까지의 구간합은 DP[b] - DP[a-1]로 정의할 수 있다.
3. 단, a가 0인 경우에는 그냥 DP[b]를 출력하면 된다.

소스 코드

import sys
n, m = map(int, sys.stdin.readline().rstrip().split())
numbers = list(map(int,sys.stdin.readline().rstrip().split()))

dp = [numbers[0]] + [0] * (n-1)

for i in range(1, n):
    dp[i] = dp[i-1] + numbers[i]

for i in range(m):
    src, dest = map(int, sys.stdin.readline().rstrip().split())
    src = src - 1
    dest = dest - 1
    if src == 0:
        print(dp[dest])
    else:
        print(dp[dest]-dp[src-1])

문제 설명

문제

상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다.

기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했다. 한 번 더 누르니 BA로 바뀌고, 그 다음에는 BAB, 그리고 BABBA로 바뀌었다. 상근이는 화면의 모든 B는 BA로 바뀌고, A는 B로 바뀐다는 사실을 알게되었다.

버튼을 K번 눌렀을 때, 화면에 A와 B의 개수는 몇 개가 될까?

입력

첫째 줄에 K (1 ≤ K ≤ 45)가 주어진다.

출력

첫째 줄에 A의 개수와 B의 개수를 공백으로 구분해 출력한다.

풀이 과정

1. K가 1일때부터 쭉 나열해 본다.

   K	값
   0	A
   1	B
   2	BA
   3	BAB
   4	BABBA
   5	BABBABAB
   6	BABBABABBABBA

2. 나열해 보면.. K가 n일때는 n-1일때의 값과 n-2일때의 값을 합쳐주었다는 것을 볼 수 있다.

3. 따라서, a의 개수를 세는 dp_a, b의 개수를 세는 dp_b를 선언해 두고,

   • dp_a[n] = dp_a[n-1] + dp_a[n-2]
   • dp_b[n] = dp_b[n-1] + dp_b[n-2]
   • dp_a[0~1] = [1, 0]
   • dp_b[0~1] = [0, 1]

4. 각각의 dp[n]을 리턴해주면 된다.

소스 코드

import sys
n = int(sys.stdin.readline().rstrip())

dp_a = [0] * (n+1)
dp_b = [0] * (n+1)

dp_a[0] = 1
dp_b[0] = 0
dp_a[1] = 0
dp_b[1] = 1

for i in range(2, n+1):
    dp_a[i] = dp_a[i-1] + dp_a[i-2]
    dp_b[i] = dp_b[i-1] + dp_b[i-2]

print(dp_a[n], dp_b[n])