크리보드는 kriii가 만든 신기한 키보드이다. 크리보드에는 버튼이 4개만 있으며, 하는 역할은 다음과 같다.
화면에 A를 출력한다.
Ctrl-A: 화면을 전체 선택한다
Ctrl-C: 전체 선택한 내용을 버퍼에 복사한다
Ctrl-V: 버퍼가 비어있지 않은 경우에는 화면에 출력된 문자열의 바로 뒤에 버퍼의 내용을 붙여넣는다.
크리보드의 버튼을 총 N번 눌러서 화면에 출력된 A개수를 최대로하는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.
출력
크리보드의 버튼을 총 N번 눌러서 화면에 출력할 수 있는 A 개수의 최댓값을 출력한다.
예제 입력과 출력
알고리즘 분류
다이나믹 프로그래밍
정답
import sys
input = lambda : sys.stdin.readline().strip()
n=int(input())
dp = [i for i in range(0, 102)]
for i in range(6, 101):
dp[i] = max(dp[i-3]*2, max(dp[i-4]*3, dp[i-5]*4))
print(dp[n])
각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.
예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.
S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.
S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.
S = 3, E = 3인 경우 1은 팰린드롬이다.
S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.
자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.
둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.
셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.
넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.
출력
총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.
예제 입력과 출력
알고리즘 분류
다이나믹 프로그래밍
정답
import sys
input = lambda : sys.stdin.readline().strip()
n=int(input())
a=list(map(int,input().split()))
m=int(input())
dp=[[0]*n for i in range(n)]
for i in range(n): # 길이가 1인 경우
dp[i][i]=1
for i in range(n-1): # 길이가 2인 경우
if a[i] == a[i+1]:
dp[i][i+1]=1
for i in range(1,n): # 길이가 3 이상인 경우
for j in range(2,i+1):
if a[i] == a[i-j] and dp[i-j+1][i-1] == 1:
dp[i-j][i]=1
for i in range(m):
s,e=map(int,input().split())
print(dp[s-1][e-1])
N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.
각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다.
가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.
출력
가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 263-1보다 작거나 같다.
예제 입력과 출력
알고리즘 분류
다이나믹 프로그래밍
힌트
정답
import sys
input = lambda : sys.stdin.readline().strip()
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
dp=[[0]*n for i in range(n)] # 방문 횟수
dp[0][0]=1
for i in range(n):
for j in range(n):
if i == n-1 and j == n-1:
break
d=i+a[i][j] # 아래쪽
r=j+a[i][j] # 오른쪽
if d < n:
dp[d][j] += dp[i][j]
if r < n:
dp[i][r] += dp[i][j]
print(dp[n-1][n-1])
add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
all: S를 {1, 2, ..., 20} 으로 바꾼다.
empty: S를 공집합으로 바꾼다.
입력
첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.
둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.
출력
check 연산이 주어질때마다, 결과를 출력한다.
예제 입력과 출력
정답
import sys
input = lambda : sys.stdin.readline().strip()
m=int(input())
s=[]
for i in range(m):
a=input().split()
if a[0] == 'all':
s.clear()
s=[i for i in range(1,21)]
continue
elif a[0] == 'empty':
s.clear()
continue
num=int(a[1])
if a[0] == 'add':
if num not in s:
s.append(num)
elif a[0] == 'remove':
if num in s:
s.remove(num)
elif a[0] == 'check':
if num in s:
print(1)
else:
print(0)
elif a[0] == 'toggle':
if num in s:
s.remove(num)
else:
s.append(num)
1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.
사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.
N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.
1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1
입력
첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.
출력
첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.
예제 입력과 출력
알고리즘 분류
순열
정답
n = int(input())
a = list(map(int, input().split()))
def _10972(a):
n=len(a)-1
i = n
while i>0 and a[i-1]>=a[i]:
i-=1
if i==0:
return False
j = n
while a[i-1]>=a[j]:
j-=1
a[i-1],a[j]=a[j],a[i-1]
j=n
while i<j:
a[i],a[j]=a[j],a[i]
i+=1
j-=1
return True
if _10972(a) is True:
for i in a:
print(i, end=' ')
else:
print(-1)
상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다.
상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.
각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다.
'.'는 빈 공간을 나타낸다.
'*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
'$'는 상근이가 훔쳐야하는 문서이다.
알파벳 대문자는 문을 나타낸다.
알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.
마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 "0"이 주어진다.
상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 빈 공간이나 문을 통해 빌딩 안팎을 드나들 수 있다. 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.
출력
각 테스트 케이스 마다, 상근이가 훔칠 수 있는 문서의 최대 개수를 출력한다.
예제 입력과 출력
알고리즘 분류
BFS
정답
from collections import deque
import sys
input= lambda : sys.stdin.readline().strip()
t=int(input())
dx=[-1,0,1,0]
dy=[0,1,0,-1]
def bfs():
de=deque()
de.append([0,0])
ch[0][0]=0
dq=[deque() for i in range(26)]
r=0
while de:
x,y=de.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < h+2 and 0 <= ny < w+2:
if a[nx][ny] == '*':
continue
if ch[nx][ny] == -1:
ch[nx][ny] = 0
if a[nx][ny] == '$':
r += 1
elif 'A' <= a[nx][ny] <= 'Z': # 문인 경우
d=ord(a[nx][ny])-ord('A')
if alp[d] is False:
dq[d].append([nx,ny])
continue
elif 'a' <= a[nx][ny] <= 'z': # 열쇠인 경우
k=ord(a[nx][ny])-ord('a')
alp[k]=True
while dq[k]:
kx,ky=dq[k].popleft()
de.append([kx,ky])
de.append([nx,ny])
return r
while t:
t -= 1
h,w=map(int,input().split())
a=[list('.'*(w+2))]
for i in range(h):
a.append(list('.'+input()+'.'))
a.append(list('.'*(w+2)))
k=input()
ch=[[-1]*(w+2) for i in range(h+2)]
alp=[False]*26
if k != '0':
for i in k:
alp[ord(i)-ord('a')]=True
print(bfs())
이 문제에서 중요한 것은 평면도에서 가로, 세로의 가장자리를 확대해서 답을 구한다는 것입니다, 가로, 세로를 확대해야 하는 이유는 빌딩 밖을 나갔다가 다시 들어와서 문을 여는 경우를 생각해야 하기 때문입니다.
배열 alp는 열쇠를 가지고 있는지 여부를 나타내기 위한 것입니다. 처음 가지고 있는 열쇠는 True로 바꿉니다.
bfs를 통해 훔칠 수 있는 문서의 최대 개수를 구합니다.
de를 통해 이동 위치를 나타내고 dq는 문의 위치를 나타냅니다.
평면도를 이동하면서 위치가 '*'인 경우는 넘어가고 그 외의 경우는 방문처리를 합니다.
위치
문서($) : 훔칠 수 있는 문서의 개수를 1 더합니다. 문(A~Z) : 열쇠가 있어서 문을 열수있는지 없는지 확인합니다. 열 수 있다면 넘어가고 열수없으면 dq에 넣어줍니다. 이는 나중에 열쇠가 생기면 dq에 있는 문을 열어줄 때 사용하기 위함입니다.
열쇠(a~z) : alp를 통해 열쇠를 True로 바꿉니다. 또한 해당 열쇠에 대한 dq를 검사해 dq에 있는 값들을 모두 방문할 수 있도록 de에 넣습니다.
