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

문제 설명

문제

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.

불은 각 지점에서 네 방향으로 확산된다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

J는 입력에서 하나만 주어진다.

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

풀이 과정

• 전체적으로 소스가 길어지는 문제인거 같음..

1. 현재 지훈이의 위치를 큐에 넣어준다.
2. 현재 불의 위치를 구해 준다.
3. bfs를 활용하여 큐의 맨 앞에서부터 위치를 빼주면서 지훈이가 갈수있는 위치를 큐에 넣어준다.
   • 이 과정을 하다 보면 이동 횟수가 바뀌는 시점이 존재한다.
   • 이동 횟수가 바뀌는 시점에 bfs를 통해 불을 확산시킨다, 이 때, 매 순간 반복문으로 불의 위치를 찾으면 시간 초과가 난다.
   • 따라서.. 한번 확산시키면서, 확산된 불의 위치 또한 큐에 저장해두어야 한다.
4. 배열의 범위를 넘게되는 순간 탈출한 것이므로 그때의 이동 횟수를 출력하고 종료한다.
5. 만약 (4)를 실행하지 않고 큐의 요소가 비게 되면 탈출이 불가능한 것이므로 IMPOSSIBLE을 출력해 준다.

• 소스가 조금 복잡하게 짜여 있음.

import sys
from collections import deque

input = sys.stdin.readline

# 불 확산 함수
Fire = deque()
def spread(matrix, R, C):
    global Fire
    stop_flag = 0
    if Fire:
        stop_flag = Fire[0][2]

    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    while Fire:
        if Fire[0][2] > stop_flag:
            break
        cx, cy, step = Fire.popleft()
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            if 0 <= nx and nx < R and 0 <= ny and ny < C:
                if matrix[nx][ny] == '.' or matrix[nx][ny] == 'J':
                    matrix[nx][ny] = 'F'
                    Fire.append([nx, ny, step+1])


R, C = map(int, input().rstrip().split())
matrix = [list(input().rstrip()) for _ in range(R)]

for i in range(R):
    for j in range(C):
        if matrix[i][j] == 'F':
            Fire.append([i, j, 0])

J_x, J_y = 0, 0
flag = False
# 지훈이의 위치 찾음
for i in range(R):
    for j in range(C):
        if matrix[i][j] == 'J':
            J_x, J_y = i, j
            flag = True
            break
    if flag:
        break


Jh_queue = deque([[J_x, J_y, 0]])
visited = set()
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
last = 0
visited.add((J_x, J_y))
answer_flag = False
answer = 0
while Jh_queue:
    jx, jy, movement_count = Jh_queue.popleft()
    # 이동 횟수가 늘어나면 불 확산
    if last != movement_count:
        spread(matrix, R, C)
        last = movement_count

    # 현재 방문하려는 위치에 이미 불 퍼진 상태면 스킵
    if matrix[jx][jy] == 'F':
        continue

    for i in range(4):
        nx, ny = jx + dx[i], jy + dy[i]
        if 0 <= nx and nx < R and 0 <= ny and ny < C:
            if matrix[nx][ny] == '.' and (nx, ny) not in visited:
                Jh_queue.append([nx, ny, movement_count+1])
                visited.add((nx, ny))
        elif 0 > nx or nx >= R or 0 > ny or ny >= C:
            answer_flag = True
            answer = movement_count + 1
            break
    if answer_flag:
        break

if answer_flag:
    print(answer)
else:
    print("IMPOSSIBLE")

문제 설명

문제

다음과 같이 정의된 수열이 있다.

• D[1] = A
• D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합

예를 들어 A=57, P=2일 때, 수열 D는 {57, 74(=5^2+7^2=25+49), 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …}이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복된다.

이와 같은 수열을 계속 구하다 보면 언젠가 이와 같은 반복수열이 된다. 이때, 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 구하는 프로그램을 작성하시오. 위의 예에서는 {57, 74, 65, 61}의 네 개의 수가 남게 된다.

입력

첫째 줄에 A(1 ≤ A ≤ 9999), P(1 ≤ P ≤ 5)가 주어진다.

출력

첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다.

풀이 과정

1. set에 반복되는 요소가 나올때까지 수열을 넣는다
   • 반복되는 요소가 나온다면 해당 요소의 값을 따로 저장만 하고 넣지는 않음.
2. 반복되는 요소에서부터 set에서 나오지 않을때까지 수열을 구하고 해당 수열을 set에서 빼준다.
3. set에 남아있는 수열이 즉, 반복되는 부분이 제외된 수열이다.

소스 코드

import sys
input = sys.stdin.readline

A, P = map(int, input().rstrip().split())

def get_next(n, p):
    nvalue = 0
    while n > 0:
        nvalue += (n % 10) ** p
        n = n // 10
    return nvalue

visited = set()

current = A
dup_start = 0
# 1. 지나간 숫자중에 하나가 다시 나타나는 경우 중복의 시작
while True:
    if current not in visited:
        visited.add(current)
    else:
        dup_start = current
        break
    current = get_next(current, P)

# 2. 중복 시작점에서 중복 끝날때까지 요소들 빼줌
while dup_start in visited:
    visited.remove(dup_start)
    dup_start = get_next(dup_start, P)

# 3. 남아있는 요소의 개수 출력
print(len(visited))

문제 설명

문제

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면

(1 2 3 4 5 6 7 8

3 2 7 8 1 4 5 6) 와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.

              순열을 배열을 이용해 (1…i…n  π1…πi…πn) 로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다.

Figure 1에 나와있는 것 처럼, 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다.

N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N (2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.

출력

각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.

풀이 과정

0. 그래프로 보면.. 1번 노드가 3번 노드와 연결되어 있다 이런식으로 해석 가능
1. 노드 1~n번째 각각에서 연결된 노드가 사이클을 형성할때까지 이동해본다.
   • dfs 사용
   • 끝나는 조건 : 이동할 때 시작 숫자 = 순열[index]
2. visited를 두어 방문했던 노드들을 다시 방문하지 않도록 처리한다.

소스 코드

import sys

input = sys.stdin.readline

T = int(input().rstrip())

def dfs(visited, sequence, start, current):
    if visited[current] == True:
        return False
    visited[current] = True
    if current == start:
        return True
    return dfs(visited, sequence, start, sequence[current])

for _ in range(T):
    N = int(input().rstrip())
    sequence = [0] + list(map(int, input().rstrip().split()))
    visited = [False] * (N+1)
    answer = 0
    for i in range(1, N+1):
        if visited[i] == False:
            answer += 1
            dfs(visited, sequence, i, sequence[i])
    print(answer)

문제 설명

문제

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])