TIL 코딩공장

20240212 백준 C언어 공부
2562번 최댓값

1. 문제
9개의 서로 다른 자연수가 주어질 때, 
이들 중 최댓값을 찾고 그 최댓값이 몇 번째 수인지를 구하는 프로그램을 작성하시오.
예를 들어, 서로 다른 9개의 자연수

3, 29, 38, 12, 57, 74, 40, 85, 61

이 주어지면, 이들 중 최댓값은 85이고, 이 값은 8번째 수이다.

2. 입력
첫째 줄부터 아홉 번째 줄까지 한 줄에 하나의 자연수가 주어진다. 
주어지는 자연수는 100 보다 작다.

3. 출력
첫째 줄에 최댓값을 출력하고, 둘째 줄에 최댓값이 몇 번째 수인지를 출력한다.

>>>코드

# include <stdio.h>
int main(void){
    int n[9], m, max;
    for (int i = 0; i < 9; i++){
        scanf("%d", &n[i]);
    }
    max = n[0], m = 0;
    for (int i = 1; i < 9; i++){
        if (max < n[i]){
            max = n[i];
            m = i;
        }
    }
    printf("%d\n", max);
    printf("%d", m+1);
    return 0;
}

>>>문제링크
https://www.acmicpc.net/problem/2562

20240325 백준 파이썬 공부
2579번 계단 오르기

1. 문제
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 
<그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 
계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

<그림 1>

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 
도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

<그림 2>

계단 오르는 데는 다음과 같은 규칙이 있다.

- 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
- 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
- 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 
하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 
첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 
이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

2. 입력
입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 
계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

3. 출력
첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

>>>코드

stair = [0] # 각 계단의 점수를 저장할 리스트
n = int(input()) # 계단의 개수
for _ in range(n): # 계단 점수 입력
    stair.append(int(input()))
dp = [0] * (n+1) # 각 계단까지의 최대 점수를 저장할 리스트
if n <= 2: # 계단의 개수가 2 이하일 경우 그냥 더하기
    print(sum(stair))
if n > 2: # 2 이상인 경우
    dp[1] = stair[1] # 첫번째 계단까지의 최대 점수
    dp[2] = stair[1] + stair[2] # 두번째 계단까지의 최대점수
    for i in range(3, n+1): # 이후 3번째 계단 부터 최대 점수 계산하는 점화식
        # i번째 계단에 올라왔다는 가정하에, 두가지 값 비교
        # i-2 번째 계단에서 올라왔을 경우의 최대값 + i번째 계단 점수 (i-1번째 계단 건너뛰기)
        # i-3 번째 계단에서 올라왔을 경우의 최대값 + i-1번째 계단 점수 + i번째 계단 점수(i-2번째 계단 건너뛰기)
        dp[i] = max(dp[i-3] + stair[i-1] + stair[i], dp[i-2] + stair[i])
    print(dp[-1]) # 결과 출력

>>> 해설
다이나믹 프로그래밍을 적극 활용해야한다
스택도 활용해보고 짝을 지어서 해보려 했으나 항상 예외가 존재하기에
1 ~ n까지의 계단을 올라갈때 가능한 점수의 최대값을 저장해서 
다음 갯수의 계단 점수의 최대값을 계산할 때 사용해야 한다.
점화식은
n-3까지의 최대값 + (n-2 건너뛰기) + n-1 + n vs n-2까지의 최대값 + (n-1 건너뛰기) + n
이라고 이해하면 된다.
그 전까지의 최대값을 구한후 한번 건너 뛰면 무조건 조건에 맞는 값을 구할 수 있다.

>>>문제링크
https://www.acmicpc.net/problem/2579