WiFi 칩 설계를 하기 위해, C 언어를 기본부터 차근히 다져보고자 한다.

많은 분들이 근본 있는 책이라고 추천하는 "C Programming : A Modern Approach"이 얼마나 근본있는 책인지 하나씩 살펴보고자 한다.

이 책을 모두 읽고 학습을 마쳤을 때, C 언어의 기초를 이해할 수 있게 되기를 바라본다.

참고 문헌

King, K. N., C Programming : A Modern Approach, W.W. Norton & Company, 2008.

1. 동치 연산자
2. 콘손로그 백틱

1. 동치 연산자

다른 언어로 개발할 때에는 없었던 표현법이라 기록해두고자 한다.

JS에는 두 가지 타입의 동치 연산자가 존재한다.

• 엄격한 동치 연산자 (Strict equality operator): ===
• 느슨한 동치 연산자 (Loose equality operator): ==

엄격한 동치 연산자는 대상들의 데이터 타입과 값까지 비교하며, 기존의 다른 언어를 활용할 때에 ==으로 많이 사용했던 것이다. 느슨한 동치 연산자의 경우는 타입 비교 없이 값만 비교하는 연산자이다.

예시로 모질라 사이트에 올라와 있는 것들을 가져왔다.

예시: 엄격한 동치 연산자 (===)

const num = 0;
const obj = new String("0");
const str = "0";

console.log(num === num); // true
console.log(obj === obj); // true
console.log(str === str); // true

console.log(num === obj); // false
console.log(num === str); // false
console.log(obj === str); // false
console.log(null === undefined); // false
console.log(obj === null); // false
console.log(obj === undefined); // false

사이트의 설명에 따르면 웬만한 것들은 모두 엄격하게 같은지 아닌지 비교한다고 한다. 다만, 예외로 재밌는 예시가 있는데 x=NaN일 때, console.log(x !== x) // true라는 점이다.

예시: 느슨한 동치 연산자 (==)

const num = 0;
const big = 0n; //BigInt
const str = "0";
const obj = new String("0");

console.log(num == str); // true
console.log(big == num); // true
console.log(str == big); // true

console.log(num == obj); // true
console.log(big == obj); // true
console.log(str == obj); // true

예시들의 변수 중 두 번째 것은 생소한 표현이라 찾아보니, BigInt라고 한다. 길이의 제약 없이 정수를 다룰 수 있게 해주는 숫자형이라고 하는데, 관련해서는 다음에 더 찾아볼 기회가 생기면 적어보려 한다.

비교하는 것들의 타입이 다를 경우 다음 규칙을 통해 변환한다고 한다.

1. Boolean -> Number
2. Number -> String
3. Number -> BigInt
4. String -> BigInt

왜 굳이 이런 기능을 넣어놨는지 아직은 잘 모르겠지만, 덕분에 오히려 예상치 못한 에러가 나는 경우가 있으니 다른 언어 생각해서 "==" 넣는 건 유의해야겠다.

2. 콘솔로그 백틱

console.log를 통해 문구를 출력할 때, 변수도 활용하는 경우가 많다. 항상, 변수에 "원하는 문구"를 +하는 형태로 출력해왔는데 문구가 더 길 경우 불편할 때가 있었다.

` 을 사용하면 두 경우를 역전해서 사용할 수 있는 방법이 있다. 이제는 문구를 " "로 감싸주는 것이 아닌, 변수를 ${ }로 감싸주는 형태로 사용하면 된다. 논문 쓸 때, latex에서 변수들은 $를 붙여줬던 것 같은데 흡사해 보인다. velog를 쓸 때도 변수 앞뒤로 $를 붙이던데, 마크다운 방식인가 싶기도 하다.

(Ex: $x$)

const blog = "diosamor";
const message = "hello";

console.log(`${blog} wants to say ${message}`);
console.log(blog + " wants to say " + message);
//diosamor wants to say hello

참고 문헌

동치 연산자

• https://developer.mozilla.org/en-US/docs/Web/JavaScript/Equality_comparisons_and_sameness
• 인프런 수업

콘손로그 백틱

• 인프런 수업

정말 어떻게 둘 다 해냈는지는 모르겠다. 계속해서 너무 정신없게 보내서 어떻게 했는지 기억도 잘 나지 않는다.

1월 첫째 주에 졸업에 관련한 행정 준비를 마칠 수 있었다. 그리고 앱 출시도 할 수 있었다.

사실, 앱의 경우에는 유튜브가 결국 1월 말 즈음에 해당 방식으로는 API를 사용하면 안 된다고 막아버려서 멈춰 있는 상태이긴 한다.

앱 출시를 한 이후에는 코딩 테스트 준비를 위해서, 정말 밥 먹고 백준 문제 풀고 다시 밥 먹고... 이것만 반복했던 것 같다. 한 달이 지나고 나니, 30단계까지 풀 수 있었고 관련해서 인상 깊었던 문제들은 블로그에도 정리했다.

2월 중순부터 코테를 운 좋게 두 군데 볼 수 있었는데, 참 어려웠다. 대부분이 반타작하는 게 고작이었다. 아무래도 코테는 또 python으로 준비했기에 참 이래저래 조급하게 보내서 더 그런 것 같기도 하다.

다른 이야기가 길었다.

결국, 굉장히 급하게 코세라를 보고 따라 하다시피 만든 나의 첫 서버는 굉장히 불안하다. 심지어 코세라 내용은 Java로 들어서, JS로 만들 때는 열심히 구글링 했다... JS도 처음 써보는 언어였는데, 다른 사람들의 코드를 보면서 어떤 의미인지 해석하면서 공부를 했다. 덕분에, JS라는 언어의 핵심을 제대로 이해하지 못하고 기능을 잘 발휘하지 못했다고 생각한다.

결국, 차근히 쌓아가면서 공부해야 한다.

백엔드 인강을 들으면서, 내가 혼자서 고민해서 만든 부분들을 어떻게 개선할 수 있을지 한 번 다시 되짚어보려 한다.

다시 힘내보자!

아직 2개월의 시간이 남았다.

출처: 백준 11286번 절댓값 힙

2. 풀이

절댓값을 이용해 최소힙 구조를 만들고, 같이 집어넣은 원래 값을 출력하는 방식으로 구현.

3. 소스코드

import sys
import heapq

input = sys.stdin.readline

heap = []
N=int(input())
for _ in range(N):
    temp = int(input())
    if temp == 0:
        if heap:
            print(heapq.heappop(heap)[1])
        else:
            print(0)
    else:
        heapq.heappush(heap,[abs(temp), temp])

4. 그 외

출처: 백준 1654번 랜선 자르기

2. 풀이

각 랜선을 정해진 크기로 잘랐을 때 몇 개가 나오는지 탐색해나가면 되는 문제이다.

이 때, 하나씩 올려가며 찾는 것은 시간이 n만큼 들기 때문에 절반씩 찾아가는 이분 탐색을 사용한다.

3. 소스코드

import sys
input = sys.stdin.readline

N, K = map(int,input().split())
lan = [int(input()) for _ in range(N)]

start = 1
end = max(lan)

while start <= end:
    mid = (start+end)//2
    temp = 0
    for i in lan:
        temp += i//mid
    if temp >= K:
        start = mid + 1
    else:
        end = mid - 1
print(end)

4. 그 외

출처: 백준 5430번 AC

2. 풀이

문제 풀이의 핵심은 뒤집는 함수를 직접 수행하기 보다는 간접적으로 결과를 뽑는데 있다.

먼저, deque를 통해 숫자를 저장한다. 그리고, R이 몇 번 실행되어야하는지 기록하는 변수를 통해 앞에서 숫자를 뺄지 뒤에서 뺄지를 정해주면 된다.

3. 소스코드

import sys
from collections import deque
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    p = input().rstrip()
    n = int(input())
    if n == 0:
        input()
        numbers = deque()
    else:
        numbers = deque(input().rstrip()[1:-1].split(","))
    count_R = 0
    check = 0
    for i in p:
        if i == 'R':
            count_R += 1
        else:
            if i == 'D' and count_R % 2 == 0:
                if numbers:
                    numbers.popleft()
                else:
                    check = 1
                    break
            else:
                if numbers:
                    numbers.pop()
                else:
                    check = 1
                    break
    if check == 1:
        print("error")
    else:
        if count_R % 2 == 1:
            numbers.reverse()
        print("["+",".join(numbers)+"]")   

4. 그 외

출처: 백준 1931번 회의실 배정

2. 풀이

최대한 많은 회의를 잡기 위해서는, 회의 시간이 짧은 것들을 최대한 집어넣으면 된다.

시작 시간으로 주어진 회의 스케쥴을 정렬하고, 끝나는 시간으로 다시 정렬해준다.

그리고 짧은 회의 시간을 가진 회의부터 차례로 카운트해주면 된다.

3. 소스코드

import sys
input = sys.stdin.readline

N = int(input())
meet = [list(map(int,input().split())) for _ in range(N)]

meet.sort(key=lambda x:x[0])
meet.sort(key=lambda x:x[1])

count = 1
end = meet[0][1]
for i in range(1,N):
    if meet[i][0] >= end:
        count +=1
        end = meet[i][1]
print(count)

4. 그 외

출처: 백준 25682번 체스판 다시 칠하기 2

2. 풀이

백준 1018번 체스판 다시 칠하기 풀이는 주어진 보드의 크기가 작았기 때문에, for문을 4개나 돌리는 방식으로 구현해도 가능하였다.

이번 문제의 경우에는 판이 커졌기 때문에 같은 방식으로 구현하면 당연히 시간 초과가 발생한다. 따라서 판이 체스판의 형태와 얼마나 다르게 생겼는지 DP 방식으로 접근하여 계산하고, 체스판을 잘라서 비교하는 형태로 풀어야 한다. 위의 설명과 같이 주어진 판의 해당 위치까지 체스판과 얼마나 다른 부분들이 있는지 개수를 저장하는 DP 2차원 리스트를 만든다. 위의 설명과 같이 구간합을 구하는 방식을 사용하여, 자른 체스판 안에 다시 칠해야 하는 부분의 개수가 얼마인지 계산할 수 있다.

체스판의 형태가 "B, W, B", "W, B, W" 두 가지 형태가 가능하므로, 두 경우에 대해서 가장 작은 개수를 구한 후 최종적인 값을 출력하면 된다.

이렇게 접근하여도, 시간 초과가 발생할 수 있으므로 PyPy3을 써야 한다.

3. 소스코드

import sys
input = sys.stdin.readline

N,M,K = map(int,input().split())
board = [list(input()) for _ in range(N)]

def min_board(color):
    dp = [[0]*(M+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(M):
            if (i+j)%2 == 0:
                temp = board[i][j] != color
            else:
                temp = board[i][j] == color
            dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j] + temp

    count = K*K
    for i in range(1,N-K+2):
        for j in range(1,M-K+2):
            count = min(count,dp[i+K-1][j+K-1] - dp[i-1][j+K-1] - dp[i+K-1][j-1] + dp[i-1][j-1])
    return count

print(min(min_board('B'), min_board('W')))

4. 그 외

체스판 칠하기 1 때보다 훨씬 복잡해졌다. 처음 문제를 접하였을 때에는, BW인 경우와 WB인 경우를 어떻게 계산해야 하나 답답했었다. 다른 분의 풀이를 보고 함수 형태로 구현하면 되는구나를 깨달았을 때는 여전히 함수로 생각하는 건 미숙하구나 싶었다.

출처: 백준 10986번 나머지 합

2. 풀이

모듈러 연산은 더하기, 빼기를 하기 전에 미리 해도 유지되는 장점이 있다.

(A-B) % M = ((A % M) - (B % M)) % M

그리고 연속된 부분 구간의 합을 쭉 DP 형태로 저장해두고, 특정 구간의 합을 구할 때는 그 DP 값을 서로 빼는 형태로 구할 수 있다. 관련된 풀이를 백준 11659번 구간 합 구하기 4에서 한 적이 있다.

따라서, 이번에는 단순히 구간 합을 저장하는 것이 아니라 M에 대한 모듈러 연산을 한 값을 저장하는 식으로 문제에 접근한다.

M으로 나눈 나머지는 0~(M-1)까지 존재할 수 있으며, 연속된 부분 구간 합에 대해 각 나머지가 나오는 개수를 DP로 세주면 된다.

그리고 같은 나머지 값을 가지는 것을 2개씩 뽑아 빼기를 진행하면 되므로, 각 개수에 대해 2개씩 뽑는 조합을 계산하면 된다. 이때, 나머지가 0이면 꼭 빼기를 진행하지 않고 하나만 골라도 괜찮으므로, dp[0]은 숫자를 하나 더 해준다.

3. 소스코드

N, M = map(int,input().split())

num = list(map(int,input().split()))

dp = [0]*M
dp[0] = 1
total = 0

for i in range(N):
    total += num[i]
    r = total % M
    dp[r] += 1

count = 0
for i in dp:
    count += i*(i-1)//2

print(count)

4. 그 외

다시금 문제를 봐도 생소하게 느껴지는 걸 보면, 많은 생각을 요구하는 문제라고 느껴진다.

출처: 백준 16139번 인간-컴퓨터 상호작용

2. 풀이

알파벳의 아스키코드와 DP를 이용하는 문제이다.

알파벳 소문자 az는 97122의 아스키코드 숫자로 표현된다. Python에서는 ord()를 이용하면 된다.

문자열을 쭉 읽으면서 각 알파벳 소문자가 몇 개 포함되어 있는지 DP 방식을 이용하여 저장하고, 원하는 구간의 값을 출력하면 된다.

Python 3로 제출할 시 시간 초과가 발생하기 때문에, PyPy3으로 제출해야 한다.

3. 소스코드

import sys

input = sys.stdin.readline

words = input().strip()
q = int(input())
n = len(words)
dp = [[0]*26 for _ in range(n)]
dp[0][ord(words[0])-97] = 1
for i in range(1,n):
    dp[i][ord(words[i])-97] = 1
    for j in range(26):
        dp[i][j] += dp[i-1][j]

for _ in range(q):
    al,l,r = input().split()
    l = int(l)
    r = int(r)
    al_index = ord(al)-97
    if l > 0:
        print(dp[r][al_index]-dp[l-1][al_index])
    else:
        print(dp[r][al_index])

4. 그 외

처음에 문제를 접했을 때에는, 아스키코드를 떠올리지 못해서 알파벳 리스트를 만들고 비교하는 식으로 구현했었다. 비교하는 과정 때문인지 시간 초과가 발생해서 다른 분들의 풀이를 참고하여 아스키코드 방식을 찾게 되었다.

지금은 list로 구현했는데, dictionary로도 구현이 가능할지 뒤에 해보면 좋을 것 같다.

출처: 백준 2559번 수열

2. 풀이

3. 소스코드

N,K = map(int,input().split())
temp = list(map(int,input().split()))

dp = [0]*(N-K+1)

for i in range(len(dp)):
    if i == 0:
        for j in range(K):
            dp[i] += temp[i+j]
    else:
        dp[i] = dp[i-1] + temp[i+K-1] - temp[i-1]
print(max(dp))

4. 그 외

출처: 백준 11659번 구간 합 구하기 4

2. 풀이

먼저, DP 접근 방식을 이용하여 선택한 숫자까지의 합을 쭉 더한 리스트를 생성한다.

주어진 i 번째 수부터 j 번째 수까지의 합을 구하고 싶다면, j 번째 DP 리스트에서 i 번째 DP 리스트를 빼주면 된다.

3. 소스코드

import sys
input = sys.stdin.readline

N,M = map(int,input().split())
numbers = list(map(int,input().split()))

dp = [0]*(N+1)
dp[1] = numbers[0]
for i in range(2,N+1):
    dp[i] = dp[i-1] + numbers[i-1]
for _ in range(M):
    i,j = map(int,input().split())
    result = dp[j]-dp[i-1]
    print(result)

4. 그 외

간단한 문제이지만, 뒤에 나올 문제들을 위해 정리하는 느낌으로 적어보았다.

출처: 백준 12865번 평범한 배낭

2. 풀이

이 문제는 2차원 DP 표를 만들어서 풀이하면 된다.

먼저, 집어넣는 물건의 개수와 최대 가방 무게를 이용하여 2차원 DP 리스트를 만든다.

DP 표를 채워나갈 때, 지금 번호의 물건을 넣을 수 없다면 이전의 DP 값을 가져오면 된다. 이전의 DP 값이 이전의 물건들을 넣었을 때 가장 큰 값이기 때문이다. 만약, 지금 번호의 물건을 새롭게 넣을 수 있는 무게가 된다면, 비교를 해야 한다.

1. 이전의 DP 값
2. 지금 물건 가치 + 지금 물건의 무게를 제외하여 집어넣었을 때 DP 값

2번이 더 크다면 2번으로 DP 값을 집어넣으면 되고, 1번이 더 크다면 이전에 채운 방식과 똑같이 채우면 된다.

모든 조합을 살펴 본 경우인 표의 가장 하단 오른쪽 부분의 값을 결과로 출력하면 된다.

3. 소스코드

n, w = map(int,input().split())

things = [list(map(int,input().split())) for _ in range(n)]
dp = [[0]*(w+1) for _ in range(n)]

for i in range(n):
    for j in range(1,w+1):
        weight = things[i][0]
        if j < weight:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j-weight]+things[i][1],dp[i-1][j])
print(dp[n-1][w])    

4. 그 외

길었던 동적계획법 1 단계가 끝났다. 문제를 잘 정의하는 것이 DP의 핵심임을 배울 수 있는 단계였다.

출처: 백준 9251번 LCS

2. 풀이

주어진 문자열을 쪼개서 끝자리를 하나식 비교해나가는 과정으로 DP 표를 만들고 풀이할 수 있다.

아래 그림은 주어진 예제의 DP 표를 만드는 과정을 그린 것이다.

3. 소스코드

word1 = input()
word2 = input()

dp = [[0]*(len(word1)+1) for _ in range(len(word2)+1)]

for i in range(1,len(dp)):
    for j in range(1,len(word1)+1):
        if word1[j-1] == word2[i-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])
print(dp[len(word2)][len(word1)])

4. 그 외

출처: 백준 2565번 전깃줄

2. 풀이

증가하는 부분 수열을 이용하여 접근하면 되는 문제이다. 백준 11053번 가장 긴 증가하는 부분 수열 문제 풀이에서 가장 긴 증가하는 부분 수열을 구하는 법을 풀이해두었다.

해당 문제에서 어떤 것을 수열도 두고, 증가하는 부분 수열을 구하면 문제 풀이에 활용할 수 있는지 고민하면 된다. 교차하는 전깃줄을 없애고 싶다면, 전깃줄이 시작하는 왼쪽 부분과 전깃줄이 끝나는 오른쪽 부분의 숫자들이 모두 오름차순으로 있다면 된다. 예제의 그림에서 왼쪽의 4번에서 출발하는 전깃줄은 오른쪽의 1번에 도착하면서, 왼쪽의 1,2,3번에서 출발하는 전깃줄보다 오른쪽의 번호가 작게 되었다. 이렇게 도착하는 전깃줄을 제거하면 교차하는 것들을 없애줄 수 있다.

따라서, 입력되는 전깃줄의 값들을 A 위치 숫자에 따라서 정렬하고, B에서 가장 긴 증가하는 부분 수열이 어떻게 되는지 살펴보면 된다. 그리고 해당 길이만큼 전깃줄을 남기면 되므로, 전체 전깃줄 개수에서 부분 수열 길이를 뺀 결과를 출력하면 된다.

3. 소스코드

n = int(input())
pos = []
dp = [1]*n
for _ in range(n):
    temp = list(map(int,input().split()))
    pos.append(temp)

pos.sort(key=lambda x: x[0])

for i in range(n):
    for j in range(i):
        if pos[i][1] > pos[j][1]:
            dp[i] = max(dp[i],dp[j]+1)
print(n-max(dp))

4. 그 외

문제를 처음 보았을 때에는 교차되는 숫자를 어떻게 세야 하나 굉장히 갑갑했었다. 부분 수열을 이런 식으로도 활용할 수 있구나를 배울 수 있는 문제였다.

출처: 백준 11054번 가장 긴 바이토닉 부분 수열

2. 풀이

이 문제는 수가 커지다가 작아지는 형태의 부분 수열을 구하는 것을 다루고 있다.

백준 11053번 가장 긴 증가하는 부분 수열 문제 풀이에서 점점 수가 커지는 부분 수열의 길이를 구하는 방법을 다뤘다. 해당 풀이를 바탕으로, 작아지는 부분 수열은 리스트를 reverse하여 구할 수 있다.

위의 설명과 같이 수열의 각 위치까지 바이토닉 부분 수열의 길이를 구하고, 최댓값을 출력하면 된다.

3. 소스코드

n = int(input())
numbers = list(map(int,input().split()))

dp = [1]*n
for i in range(n):
    for j in range(i):
        if numbers[i] > numbers[j]:
            dp[i] = max(dp[i],dp[j]+1)

numbers.reverse()
dp_reverse = [1]*n
for i in range(n):
    for j in range(i):
        if numbers[i] > numbers[j]:
            dp_reverse[i] = max(dp_reverse[i],dp_reverse[j]+1)

dp_total = []
for i in range(n):
    dp_total.append(dp_reverse[i]+dp[n-i-1]-1)
print(max(dp_total))

4. 그 외

출처: 백준 11053번 가장 긴 증가하는 부분 수열

2. 풀이

이 문제의 경우에는 어떤 수열인지는 구할 필요가 없고, 길이만 즉 포함된 숫자의 개수만 구하면 된다.

구하려고 하는 부분 수열은 계속해서 증가하는 형태여야 하기 때문에, 살펴보려 하는 숫자보다 앞에 있는 숫자들 중 작은 것이 어떤 것들이 있는지 살피면 된다. 또한, 앞선 숫자들의 경우에도 그 숫자들보다 앞에 있는 숫자들은 작아야 한다.

Ex) (30,10,20,50) 같은 경우라면 30은 50보다 작긴 하지만, 부분 수열에 들어갈 수 없게 된다.

즉, 숫자들을 살필 때에 앞선 숫자가 지금 선택한 숫자보다 작다면, 앞선 숫자는 몇 개의 숫자를 부분 수열로 가지고 있는지 살핀 후 1개를 추가하면 되는 것이다. 다만, 다른 경우의 부분 수열 길이가 더 길 수도 있기 때문에 기존에 저장해오던 값과 새로 계산한 값 중 어떤 것이 더 큰 지 비교하는 과정이 필요하다.

3. 소스코드

n = int(input())
numbers = list(map(int,input().split()))

dp = [1]*n
for i in range(n):
    for j in range(i):
        if numbers[i] > numbers[j]:
            dp[i] = max(dp[i],dp[j]+1)
print(max(dp))

4. 그 외

부분 수열을 구하는 문제는 계속해서 유형을 달리해서 나왔던 것으로 기억한다. 그때마다 다르게 접근하는 것이 재밌게 느껴진다.

출처: 백준 2156번 포도주 시식

2. 풀이

연속으로 3잔을 마실 수는 없기 때문에 포도주를 마시는 방법은 총 3가지로 분류할 수 있다.

1. 지금 잔과 이전 잔을 마신다.
2. 지금 잔만 마신다.
3. 지금 잔을 마시지 않는다.

문제를 DP 방식으로 접근해, 현재까지 마신 포도주의 양을 쭉 저장해온다고 했을 때, 각 상황에 대해 더해줘야 하는 양은 아래와 같다.

1. 지금 잔 + 이전 잔 + 3개 잔 이전에 마셔온 양
2. 지금 잔 + 2개 잔 이전에 마셔온 양
3. 이전 잔까지 마셔온 양

각 상황에 대해서 값을 구한 후, 최댓값을 계속해서 마셔온 양에 저장하고 최종 값을 출력하면 된다.

3. 소스코드

n = int(input())

dp = [0]*n
number = [0]*n
for i in range(n):
    number[i] = int(input())
    if i == 0:
        dp[0] = number[0]
    elif i == 1:
        dp[1] = number[0] + number[1]
    elif i == 2:
        temp1 = number[i]+number[i-1]
        temp2 = number[i]+dp[i-2]
        temp3 = dp[i-1]
        dp[i] = max(temp1,temp2,temp3)
    else:
        temp1 = number[i]+number[i-1]+dp[i-3]
        temp2 = number[i]+dp[i-2]
        temp3 = dp[i-1]
        dp[i] = max(temp1,temp2,temp3)
print(dp[n-1])

4. 그 외

백준 2579번 계단 오르기 문제와 비슷한 부분이 많다. 이전 문제는 현재 계단을 오르지 않는다는 선택지가 없지만, 이 문제의 경우는 지금 와인 잔을 마시지 않는다는 선택지가 있어서 경우의 수가 하나 더 추가된다.

계단 오르기 문제는 백준 2579번 계단 오르기 문제 풀이에 풀이를 해두었다.

출처: 백준 10844번 쉬운 계단 수

2. 풀이

계단수를 만드는 방법을 숫자의 길이가 1일 때부터 생각해 보자.

숫자의 길이가 1이라면, 1~9까지 9개의 숫자가 가능하다.

다음 길이가 2일 때는, 1~8까지의 숫자에 하나씩 차이 나는 경우를 붙이는 것을 생각해 볼 수 있다.

Ex) 01, 21 , ... , 78, 98

길이가 2일 때는 01이 불가능한 경우이긴 하지만, 길이가 3일 때부터는 가능한 경우가 생기니 예시로 적어보았다. (101과 같은 경우가 가능해진다.)

그리고 숫자가 0이나 9의 경우에는 하나씩만 붙일 수 있다.

Ex) 10, 89

즉, 계단 수의 숫자를 계산하는 방법은 끝의 자릿수가 1~8일 때는 각 끝자리 수의 앞뒤 숫자로 끝나던 계단 수의 개수를 더해주면 된다. 그리고 끝의 자릿수가 0과 9라면 각 끝자리수가 1과 8로 끝나는 계단 수의 개수를 가져오면 된다.

최종적으로 입력 길이에 맞는 계단 수의 숫자를 모두 더해주고, 주어진 숫자로 나눈 나머지를 출력한다.

3. 소스코드

n = int(input())

dp = [[0]*10 for _ in range(n+1)]
for i in range(1,10):
    dp[1][i] = 1

MOD = 1000000000
for i in range(2,n+1):
    for j in range(10):
        if j == 0:
            dp[i][j] = dp[i-1][1]
        elif j == 9:
            dp[i][j] = dp[i-1][8]
        else:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

print(sum(dp[n]) % MOD)

4. 그 외

출처: 백준 2579번 계단 오르기

2. 풀이

계단을 오를 때, 지금 있는 위치에 오기 위해서는 두 가지의 경로가 있다.

1. 2칸 전에서 2칸을 한 번에 오기
2. 3칸 전에서 2칸을 한 번에 옮겨 1칸 전으로 이동하고, 마저 1칸을 이동해 지금 칸으로 오기

연속된 세 개의 계단을 밟으면 안 되기 때문에, 1칸씩 쭉 이동해 오는 건 불가능하다.

앞서 소개한 두 가지 경로 중에 저 큰 점수를 받을 수 있는 경로를 쭉 저장하다가, 마지막 계단의 값을 출력하면 된다.

3. 소스코드

n = int(input())
score = [0]*n
stair = [0]*n
for i in range(n):
    stair[i] = int(input())
    if i == 0:
        score[i] = stair[i]
    elif i == 1:
        score[i] = stair[i]+stair[i-1]
    elif i == 2:
        score[i] = max(stair[i]+stair[i-2],stair[i]+stair[i-1])
    else:
        temp2 = score[i-2] + stair[i]
        temp3 = score[i-3] + stair[i-1] + stair[i]
        score[i] = max(temp2,temp3)
print(score[n-1])

4. 그 외