오늘 푼 문제는 구름 LEVEL의 문제들입니다. 이번주 토요일에 구름 IDE를 사용하는 코딩테스트가 있기 때문에,
환경에 익숙해질 겸 모든 문제를 풀어보려고 합니다.
문제 수가 많지 않고 난이도도 낮은 편인 것 같아서 다 풀려고 합니다.
- 어려운 문제
팩토리얼을 계산하여 모든 자리수의 합이 한자리 수가 될 때까지 반복하는 문제입니다.
팩토리얼은 100 만 넘어가도 수가 급격하게 커집니다.
근데 N의 범위가 10000까지 이므로, 이를 구할 수 있는 다른 방법이 무조건 있을 거라고 생각하고
문제를 읽습니다.
알고리즘 적으로 해결할 방법이 떠오르지 않아서, 입력값을 보고 규칙이 있나 찾아봅니다.
3! -> 6, 4! -> 6, 5! ->3 , 6!->9, 7!->9, 8!->9, 9!->9
6!부터는 모든 자리수의 합이 9가 되는 것을 알 수 있습니다. 10진법에서 9의 배수는 각 자리수의 합이
무조건 9가 되기 때문에 3이 두번 들어가는 6!부터는 모두 9가 됩니다. 따라서 나머지는 if문으로 걸러주고
6이상의 입력은 모두 9를 출력하면 됩니다.
3의 배수는 각 자리수의 합이 3의 배수가 되는 것은 알고 있었는데, 9의 배수 규칙이 있다는 사실은 처음 알았습니다.
import sys
n = int(sys.stdin.readline())
if n==0: print(1)
elif n<=2: print(n)
elif n<=4: print(6)
elif n==5: print(3)
else: print(9)
- 징검다리 건너기
이 문제는 1차원 수열에서 접한는 독극물의 양이 최소가 되도록 다리를 건너는 문제입니다.
한 번 건널 때 최대 3 길이까지 점프 가능함은 전형적인 DP문제에서 보이는 패턴입니다.
dp[i] 를 i 번째 징검다리를 밟았을 때 얻는 최소의 독극물 이라고 정의합니다.
i번째를 밟는다는 것은 그 전 단계에서 i-1 에서 왔거나, i-2, i-3에서 올 수 있습니다.
따라서 점화식은 아래와 같습니다.
dp[i] = min(min(dp[i-1],dp[i-2]),dp[i-3]) + p[i] ( i >= 3)
i가 3보다 작을 경우에는 자기 자신이 됩니다.
그런데 n의 값이 3보다 작은 경우가 들어온다면, 어떤 독극물도 안건들이고 바로 건널 수 있어서 0 을 출력합니다.
import sys
n = int(sys.stdin.readline())
p = list(map(int,sys.stdin.readline().split()))
dp = [1e10 for _ in range(n)]
if n>=3:
for i in range(3): dp[i] = p[i]
for i in range(3,n):
dp[i] = min(min(dp[i-1],dp[i-2]),dp[i-3]) + p[i]
print(min(dp[-1],min(dp[-2],dp[-3])))
else:
print(0)
이 문제를 보았을 때 구름에서 레벨 3정도는 백준 기준 실버 2-4 사이로 보입니다.
- 불이야 !!
이 문제는 주인공이 &에 있을 때 가장 가까운 @의 거리를 구하는 문제입니다.
보자마자 전형적인 BFS 문제라고 생각하여 예시와 같이 @을 기준으로 BFS로 &을 탐색하게 되면 시간초과가 발생합니다.
간과하기 쉬운 조건이 저 경우에는 주인공의 개수와 불의 개수가 단 한개씩만 존재할 경우, 어느 출발점을 삼아서 BFS를 하더라도 같은 결과가 나옵니다.
따라서 예시의 그림을 무시하고, 주인공을 기준으로 가장 빠르게 불을 만났을 경우를 return 문으로 빠져나와 줍니다.
import sys
from collections import deque
def bfs(x,y):
v[x][y] = 1
q = deque()
q.append((x,y))
while q:
x,y = q.popleft()
for i in range(4):
nx,ny = x+dx[i],y+dy[i]
if 0<=nx<n and 0<=ny<m and (g[nx][ny] == '.' or g[nx][ny]=='@') and v[nx][ny] == 0:
v[nx][ny] = v[x][y] + 1
if g[nx][ny] == '@':
print(v[nx][ny]-2)
exit(0)
q.append((nx,ny))
return (-1,-1)
n,m = map(int,sys.stdin.readline().split())
g = [sys.stdin.readline().rstrip() for _ in range(n)]
v = [[0 for _ in range(m)] for _ in range(n)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
r,c = 0,0
find = []
for i in range(n):
for j in range(m):
if g[i][j] == '&':
bfs(i,j)
print(-1)
만약에 불을 기준으로 주인공을 찾는다면, 7번 8번 10번 테케에서 시간초과가 발생합니다. 적절한 visit 배열을 최적화하고 BFS 중간에 return 문까지 넣는다면 7번까지도 통과합니다.
주인공을 기준으로 불을 찾으면 모든 테스트가 충분한 시간 내에 통과가 됩니다.
BFS 를 기계적으로 탐색하는 것이 아닌, 어떤 도착점과 출발점이 유일한지 판단하여 출발점을 정하는 것도 중요하다는
것을 깨달았습니다.
