2018. 8. 13. 00:27ㆍProgramming/Algorithm
문제 1463 - 1로 만들기
링크 - https://www.acmicpc.net/problem/1463
소스코드
import sys
import math
num = int(sys.stdin.readline())
arr = [0]*(num+1)
for i in range(1, num+1):
if i == 1:
continue
val = []
if i % 3 == 0:
val.append(arr[i//3] + 1)
if i % 2 == 0:
val.append(arr[i//2] + 1)
val.append(arr[i-1] + 1)
arr[i] = min(val)
sys.stdout.write(str(arr[num]))
코멘트
딱히 없다. 다이나믹 프로그래밍의 전형적인 예.
문제 11726 - 2xN 타일링
링크 - https://www.acmicpc.net/problem/11726
소스코드
import sys
def fibo(n):
def fibo_help(a, b, n):
return fibo_help(b, a+b, n-1) if n>0 else a
return fibo_help(0, 1, n)
num = int(sys.stdin.readline())
sys.stdout.write(str(fibo(num+1)%10007))
코멘트
피보나치로 풀 수 있는 문제. 피보나치 구현은 tail-recursion(꼬리 재귀)으로 구현했는데, 인터넷에 돌아다니던 방법을 참조했다. 다른 재귀 호출에 비해 더 빠르다... 고 한다. 왜 피보나치인지 모르겠으면 그림을 그려보면 감이 올 것이다. i-2 번째일때 추가적으로 놓을 수 있는 타일은 하나만 있다고 간주해야한다. i-1 번째와 겹치는 것이 있으므로 제거하고 나면 그렇게 된다.
문제 11727 - 2xN 타일링 2
링크 - https://www.acmicpc.net/problem/11727
소스코드
import sys
num = int(sys.stdin.readline())
arr = [0] * (num+1)
arr[1] = 1
if num > 1:
arr[2] = 3
for i in range(3, num + 1):
arr[i] = arr[i-2] * 2 + arr[i-1]
sys.stdout.write(str(arr[num]%10007))
코멘트
피보나치의 변형 문제라고 볼 수 있을 듯. i-2번째에서 놓을 수 있는 타일의 가지수가 2개가 되어버리므로 *2가 붙는다.
문제 9095 - 1, 2, 3 더하기
링크 - https://www.acmicpc.net/problem/9095
소스코드
import sys
arr = [0] * 11
arr[1] = 1
arr[2] = 2
arr[3] = 4
for i in range(4, 11):
arr[i] = arr[i-3] + arr[i-2] + arr[i-1]
num = int(sys.stdin.readline())
for i in range(num):
line = int(sys.stdin.readline())
sys.stdout.write(str(arr[line]) + '\n')
코멘트
멍청하게 stdout에서 개행문자를 안 넣어서 틀렸던 문제. 백준 저지에서 '출력 형식이 잘못되었습니다' 가 뜨는 경우는 값 자체는 옳으나 공백 문자의 위치나 개수가 다를 때 등장한다. 즉, 개행문자까지 체크를 해주진 않는다. 개행을 하지 않으면 아예 틀렸다고 나온다. print() 쓰면 이럴 걱정 없다.
문제 11052 - 붕어빵 판매하기
링크 - https://www.acmicpc.net/problem/11052
소스코드
import sys
num = int(sys.stdin.readline())
tai = [0] * (num+1)
sale = [None] * (num+1)
for i in range(num+1):
sale[i] = [0]*(num+1)
line = list(sys.stdin.readline().strip().split())
for i in range(1, num + 1):
tai[i] = int(line[i-1])
sale[1][1] = tai[1]
for i in range(1, num + 1):
for j in range(1, num+1):
arr = []
if j >= i:
arr.append(sale[i][j-i] + tai[i])
arr.append(sale[i-1][j])
arr.append(sale[i][j-1])
sale[i][j] = max(arr)
sys.stdout.write(str(sale[num][num]))
코멘트
다이나믹 프로그래밍의 대표 문제인 가방에 물건 담기 or 거스름돈 계산하기 문제 응용편이다. 비슷한 문제를 풀어봤으면 크게 어렵진 않을 듯.
문제 10844 - 쉬운 계단 수
링크 - https://www.acmicpc.net/problem/10844
소스 코드
import sys
num = int(sys.stdin.readline())
arr = [1] * 10
arr[0] = 0
for i in range(1, num):
new_arr = [0]*10
for (j, e) in enumerate(arr):
if j == 0:
new_arr[1] += e
elif j == 9:
new_arr[8] += e
else:
new_arr[j-1] += e
new_arr[j+1] += e
arr = new_arr
sys.stdout.write(str(sum(arr)%1000000000))
코멘트
처음에 단순하게 피보나치 응용이겠거니.. 싶었는데 자꾸 틀려서 뭔가 했다. 직접 종이에 그림 그려보면서 해보니 아, 하고 느낌이 왔다. 0부터 9까지 숫자 배열을 만든 다음에, 반복문을 돌면서 다음 배열의 값을 올려줘야 했다. 전형적인 Bottom-up 프로세스고, 이 때 9와 0은 각각 8과 1이라는 다음 선택지밖에 없으므로 이 부분을 핸들링 해야한다. new_arr를 만들지 않고 처음부터 2차원 list를 만들어도 무방하다.
파이썬의 장점을 체험할 수 있는 시간 중 하나이기도 한데, 다른 언어에서는 중간에 값이 너무 커져서 오버플로우가 필연적으로 발생하게 된다. 파이썬의 int는 byte 수가 한정되어있지 않고 탄력적으로 늘어나므로 오버플로우 걱정을 안 해도 된다. 그래도 메모리를 조금이라도 아끼고 싶으면 중간중간에 mod를 써도 나쁘진 않을듯.
문제 11057 - 오르막 수
링크 - https://www.acmicpc.net/problem/11057
소스코드
import sys
num = int(sys.stdin.readline())
arr = [None] * (num + 1)
arr[1] = [1] * 10
if num > 1:
for i in range(2, num+1):
arr[i] = [0] * 10
for i in range(2, num+1):
for (j, e) in enumerate(arr[i-1]):
for k in range(j, 10):
arr[i][k] += e
sys.stdout.write(str(sum(arr[num])%10007))
코멘트
위의 계단 수와 크게 다르지 않다. 차이점은 첫 숫자가 0도 가능하다고 전제한 것이고, 각 숫자들은 자기보다 이상의 값을 같는 숫자들에게 1 씩 더해준다는 점. 여기선 2차원 list로 해결했다.
문제 2193 - 이친수
링크 - https://www.acmicpc.net/problem/2193
소스코드
import sys
num = int(sys.stdin.readline())
arr = [[0, 0]] * (num+1)
arr[1] = [0, 1]
if num > 1:
for i in range(2, num+1):
z = arr[i - 1][0]
x, y = arr[i-1]
arr[i][0] = x + y
arr[i][1] = z
# arr[i][0] = sum(arr[i-1])
# arr[i][1] = arr[i-1][0] 을 하면 잘못된 값이 나왔다. 왜지?
sys.stdout.write(str(sum(arr[num])))
코멘트
아직까지 미스테리로 남은 문제 중 하나
주석 처리된 부분처럼 첫 시도를 했다가 arr[i]번째가 잘못 입력되어서 위처럼 x, y, z라는 지역변수를 따로 선언해서 처리했다.
한가지 이해가 안가는 부분은 sum(arr[i-1])을 시행했다고 arr[i]의 값 자체가 변해버린 점인데, 당최 어떤 원리로 이렇게 바뀐 것인지 모르겠다. 애초에 파이썬의 변수가 모두 reference 형태라서 특정 변수의 조작이 다른 변수의 값도 바뀌게 할 수 있는 것은 아는데, 아직 제대로 할당도 안된 arr[i]의 값이 왜...?