2023년 9월 16일 알고리즘 문제풀이
문제 1 백준 1030
1차 시도
나의 생각
분할정복으로 풀면 되겠다고 생각했다. 정사각형 한 변의 길이는 1초마다 n이 곱해져 결국 s초 후 n의 s제곱 형태가 된다. s는 최대 10, n은 최대 8이므로 한 변의 길이는 최대 2의 30제곱이나 된다. 전체 정사각형 배치를 그린 후 원하는 부분만 출력하기엔 너무 크다는 뜻이다. 문제에서 출력하라고 요구하는 부분만 출력해야 한다.
이 부분이 너무 어려워서 다른 사람들의 풀이를 보고 공부한 코드이다. l은 위에서 말했던 n의 s제곱이자 s초 후 정사각형의 한 변의 길이이다. main 함수는 평면의 한 변의 길이와 검은색인지 확인할 곳의 행렬을 x,y로 받는다. 중앙의 k x k 크기의 사각형에 포함된다면 검은색이므로 1을 반환한다.
결국 이 문제는 ‘문제에서 원할 떄의 사각형에서 출력해야하는 부분이 검은색일지 아닐지만 판단해서 출력함’으로서 문제를 해결한다.
결과
이해
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import sys
s, n, k, r1, r2, c1, c2 = map(int, sys.stdin.readline().split())
l = n**s
def main(t,x,y):
if t == 1:
return 0
tmp = t//n
if (tmp * (n-k)//2 <= x < tmp * (n+k)//2) and (tmp * (n-k)//2 <= y < tmp * (n+k)//2):
return 1
return main(tmp,x%tmp,y%tmp)
for i in range(r1, r2+1):
for j in range(c1, c2+1):
print(main(l,i,j), end='')
print()
문제 2 백준 1931
1차 시도
나의 생각
가장 빠르게 시작하는 수업의 끝을 기준으로 그 수업이 끝나면 다음 시작하는 수업중 가장 빠른것을 시작하며 갯수를 세는 간단한 문제였다. arr을 정렬할 때 처음에는 한번만 해서 틀렸었다. arr.sort()을 통해 0번 index를 기준으로 정렬을 한 후 1번 index를 기준으로 정렬해야 한다. 그래야 1번 index가 같은 원소들이 0번 index를 기준으로 정렬된다. 바로 1번 index를 기준으로 정렬하면 같은 1번 index를 가진 원소들끼리 0번 index의 정렬이 되지 않는다.
예시 1 : 두번 정렬
arr = [(3, 2), (1, 2), (4, 4), (2, 4)] 을 0번 index를 기준으로 정렬하면
arr = [(1, 2), (2, 4), (3, 2), (4, 4)]이다. 다시 1번 index를 기준으로 정렬하면
arr = [(1, 2), (3, 2), (2, 4), (4, 4)]가 나온다.
예시 2 : 한번 정렬
arr = [(3, 2), (1, 2), (4, 4), (2, 4)] 똑같은 배열을 바로 1번 index를 기준으로 정렬하면
arr = [(1, 2), (3, 2), (4, 4), (2, 4)] 이렇게 3번, 4번 index가 달라질 수 있음에 유의하자.
결과
정답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import sys
n = int(sys.stdin.readline())
arr = []
for _ in range(n):
arr.append(list(map(int,sys.stdin.readline().split())))
arr.sort()
arr.sort(key = lambda x : x[1])
cnt = 1
t = arr[0][1]
for i in range(1,n):
if arr[i][0] >= t:
t = arr[i][1]
cnt += 1
print(cnt)
문제 3 백준 2253
1차 시도
나의 생각
DP를 이용하되, 그 돌에 도착할 때까지의 최소 점프 횟수와 도착 당시 뛰었던 점프 거리를 저장해야겠다고 생각했다. 어떤 돌에 도착했을 때 방금 점프를 x만큼 뛰었더라면 그 돌에서는 x-1,x,x+1만큼 이동할 수 있다. 그 다음 돌에도 이 부분을 표시해야 할 것 같다. 그런데 코드로 어떻게 작성해야 할지 참 어려웠다. 어떤 좌표 i를 파악하기 위해선 이전 돌 어디를 봐야하나 고민이 들었다. 바로 전 돌인 i-1이랑은 무관한 것이 점프 거리에 대한 제한이 있어서..
결국 나는 dp가 나타내는 ‘값’을 그곳까지 도달하는데 점프의 횟수로 나타내었다. 왜냐하면, 도달하는데 다양한 방법이 있을것이다. 그럴 때 가장 적은 횟수의 방법만 남겨논다면 어떤 곳은 갈 수 있음에도 못가는 것으로 처리될 수 있다고 생각했다. 예를 들어서 i 번째 돌에 10번 째에 9만큼 점프를 뛰어 도착하는 경우와 20번째에 3만큼 점프를 뛰어 도착하는 방법 두 가지가 있을 수 있다. 물론 더 많을 수도 있고. 여기서 10번 점프 뛴 것만 생각한다면, 다음 할 수 있는 점프는 8,9,10 이기 때문에 i+8, i+9, i+10 번째 돌만 업데이트된다. 하지만 i+3 번째 돌도 갈 수 있다. 21번 점프를 뛰어서 가야하긴 하지만. 이 방법이 유일하게 i+3 번째 돌을 가고자 하는 방법이라면 문제가 생길 수 있다.
따라서 dp[i][x]는 i번째 돌에 마지막 점프 거리를 x로 해서 도착한 경우의 점프 횟수를 나타낸다. 그렇다면 dp[i]는 몇개의 원소를 가지고 있어야 할까? 이 말은 점프 거리가 어느정도까지 길어질 수 있을까를 말한다. 점프거리가 100이 가능하면 dp[i][100] 도 만들어 놔야 index error가 발생하지 않을 것이다.
시작한 이후 계속 점프 거리를 1씩 늘려가며 전진한다고 생각해보자. 이 방법은 가장 마지막까지 도달하는 빠른 방법이다. 물론 n번째 돌에 착지하지 못하고 지나갈 수 도 있지만 말이다. 점프 거리를 1씩 늘려가며 x까지 도달했을 때의 이동 거리는 1+2+3+..+x = x(x+1)/2 이다. 이 값은 돌의 갯수인 n을 넘을 수 없다. 이 관계식을 통해 x의 최댓값을 n을 통해 표현할 수 있고 아래 코드에 나오는 limit이 최댓값을 의미한다.
dp[i][jump]는 방금 jump 만큼 뛰어서 i번째 돌에 도착했다는 것을 의미하는데, 이를 통해 직전의 점프를 유추할 수 있다. 점프 거리는 최대 1만큼 변할 수 있으므로 그 전 칸에 도착했을 때 점프 거리는 jump-1 , jump, jump+1 였을 것이다. 전 칸의 위치는? 방금 jump만큼 뛰어서 i에 왔으니 i-jump가 이전 칸일 것.
코드는 아래와 같다.
결과
정답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import sys
n, m = map(int, sys.stdin.readline().split())
x = []
for _ in range(m):
x.append(int(sys.stdin.readline()))
limit = int(((8*n+1)**0.5-1)//2)+1
dp = [[1e9 for _ in range(limit+1)] for _ in range(n+1)]
dp[1][0] = 0
for i in range(2,n+1):
if i in x:
continue
for jump in range(1,limit+1):
dp[i][jump] = min(dp[i-jump][jump-1],dp[i-jump][jump],dp[i-jump][jump+1])+1
if min(dp[n]) != 1e9:
print(min(dp[n]))
else:
print(-1)
