2018. 08. 15 백준 저지 알고리즘 정리(파이썬)

문제 1912 - 연속합

링크 - https://www.acmicpc.net/problem/1912

소스코드

import sys


num = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().rstrip().split()))

D = [0 for i in range(num)]
D[0] = arr[0]

for i in range(1, num):
    D[i] = max(D[i-1] + arr[i], arr[i])

sys.stdout.write(str(max(D)))

코멘트

솔직히 봐도 봐도 봐도 계속 틀려서 고심 끝에 답을 봐야했던 문제였다. 문제 접근 방법부터가 잘못 되었었다. 나는 D를 "해당 index까지 범위에서 가장 큰 연속합"으로 정의하고 문제를 풀었었는데, 다른 사람 답을 보니 D를 "해당 index를 포함한 수열 중에서 가장 큰 연속합"으로 정의해놓고 풀었었다. 내 방식대로 하면 D에 값 뿐만 아니라 index까지 따로 저장하고, 이중반복문까지 써야하고 난리도 아니었는데, 후자의 방법으로 푸니 너무 간단하게 답이 나왔다. 그래도 지난달에는 프로그래밍 참 내 길같다고 생각했는데, 알고리즘만 계속 풀고 있자니 아닐 수도 있겠단 생각도 든다.

문제 2579 - 계단 오르기

링크 - https://www.acmicpc.net/problem/2579

소스코드

import sys


stair = []
num = int(sys.stdin.readline())

for i in range(num):
    stair.append(int(sys.stdin.readline()))

D = [[0, 0] for i in range(num)]

if num < 3:
    sys.stdout.write(str(stair[0] + stair[1]))
    exit()

D[0] = [stair[0], 0]
D[1] = [stair[0] + stair[1], stair[1]]

for i in range(2, num):
    D[i][0] = D[i-1][1] + stair[i]
    D[i][1] = max(D[i-2]) + stair[i]

sys.stdout.write(str(max(D[num-1])))

코멘트

바로 이전문제에서 현타가 너무 강하게 온 탓인지, 이 문제는 생각보다 금방 풀렸다. 그림 그려놓고 하니 바로 감이 왔는데, 와인 문제와 비슷한 듯하다. 역시나 D는 "해당 계단을 포함하면서 만들 수 있는 최대의 점수"로 정의해놓고 풀었다. 내부의 0번 인덱스와 1번 인덱스는 계단 하나로 도달하느냐, 계단 두개로 도달하느냐의 차이.

문제 1699 - 제곱수의 합

링크 - https://www.acmicpc.net/submit/1699/9766507

소스코드

import sys
import math


num = int(sys.stdin.readline())
square_arr = [x**2 for x in range(math.ceil((10**0.5)*100) + 1)]
D = [0 for i in range(num+1)]

D[1] = 1

if num < 2:
    sys.stdout.write("1")
    exit()

D[2] = 2

for i in range(2, num+1):
    x = math.inf
    limit = -1
    for (j, e) in enumerate(square_arr):
        if e == i:
            D[i] = 1
            break
        elif e > i:
            limit = j
            break

    if limit == -1:
        continue
    else:
        for j in range(1, limit):
            y = square_arr[j]
            z = 1 + D[i-y]
            if z < x:
                x = z

        D[i] = x

sys.stdout.write(str(D[num]))

코멘트

처음에 제출했을 때 정답 처리는 됐는데 시간이 6576ms가 나와서 엉?! 했었다. 초반엔 시간복잡도 O(N^2)로 짜긴 했었지만 설마 이 정도라니.. 제곱수들을 중점으로 계산하는 방식으로 바꾸니 훨씬 빨라졌다.

또 제곱수를 그때그때 계산하는 게 싫어서 애초부터 입력범위 내의 제곱수를 전부 만들어두고 시작했다. 그래서 그런지 메모리 사용량이 아슬아슬하게 128MB 아래 선으로 나왔다. 채점결과를 보니 C++ 만세가 따로 없다. 이렇게 빠르다니.. 역시 뭐니뭐니해도 효율성의 최고봉은 C++ 못 따라가나 보다.