[2025 1학기 알고리즘 스터디] 김민재 #2주차

가장 긴 증가하는 부분 수열

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n+1];
        int[] dp = new int[n+1];
        for (int i = 1; i <= n; i++) {
            arr[i] = sc.nextInt();
        }

        int maxLength = 0;

        for (int i = 1; i <= n; i++) {
            dp[i] = 1;
            for (int j = 1; j <=i; j++) {
                if (arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            maxLength = Math.max(maxLength, dp[i]);
        }
        System.out.println(maxLength);
    }
}

 

 

1로 만들기

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] dp = new int[n+1];    //n만큼 배열 만들기
        dp[1] = 0;  //1은 계산할 것이 없으므로 0

        for (int i = 2; i <= 10; i++) {

            dp[i] = dp[i-1] + 1;    // 기본적으로 1뺀다 생각하고 이전 값에 더하기 1

            if (i % 2 == 0) {   // 2으로 나눠지면 1뺀 것과 2로 나눈것 중 최소값 선택
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            }

            if (i % 3 == 0) {   // 3으로 나눠지면 1뺀 것과 3으로 나눈것 중 최소값 선택
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            }
        }

        System.out.println(dp[n]);

    }
}

 

처음에는 이렇게 짰지만 수정해서 통과~~

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] dp = new int[n+1];    //n만큼 배열 만들기
        dp[1] = 0;  //1은 계산할 것이 없으므로 0

        for (int i = 2; i <= n; i++) {

            dp[i] = dp[i-1] + 1;    // 기본적으로 1뺀다 생각하고 이전 값에 더하기 1

            if (i % 2 == 0) {   // 2으로 나눠지면 1뺀 것과 2로 나눈것 중 최소값 선택
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            }

            if (i % 3 == 0) {   // 3으로 나눠지면 1뺀 것과 3으로 나눈것 중 최소값 선택
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            }
        }

        System.out.println(dp[n]);

    }
}

 

 

계단 오르기

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		int N = Integer.parseInt(br.readLine());
 
		int[] DP = new int[N + 1];
		int[] arr = new int[N + 1];
 
 
		for (int i = 1; i <= N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
 
		// index = 0 은 시작점
		DP[1] = arr[1];
		
		// N 이 1이 입력될 수도 있기 때문에 예외처리를 해줄 필요가 있음
		if (N >= 2) {
			DP[2] = arr[1] + arr[2];
		}
 
		for (int i = 3; i <= N; i++) {
			DP[i] = Math.max(DP[i - 2] , DP[i - 3] + arr[i - 1]) + arr[i];
		}
 
		System.out.println(DP[N]);
 
	}
 
}