[코테 매일 풀기 12일차] 1120

1. 백준 2579 계단오르기

아이디어

• dp[n]까지 점화식 만들고, dp[n]출력
• 점화식: dp[i] = Math.max(dp[i-3] + stairs[i-1] + stairs[i] , dp[i-2] + stairs[i]);

package boj_silver.p2579_계단오르기;

import java.util.Scanner;

public class Review1 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] stairs = new int[n+1];
        for (int i = 1; i<=n; i++){
            stairs[i] = scan.nextInt();
        }
        //dp 초기화
        int [] dp = new int[n+1];
        //만약 계단이 적다면 !
        dp[0] = 0;
        if (n>=1){
            dp[1] = stairs[1];
        }
        if(n>=2){
            dp[2] =  stairs[1] + stairs[2];
        }
        if (n>=3){
            //dp 식
            for (int i = 3; i<=n; i++){
                dp[i] = Math.max(dp[i-3] + stairs[i-1] + stairs[i], dp[i-2] + stairs[i]);
            }

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


    }
}

Bottom-Up DP (내 방식 개선)

int[] dp = new int[n+1]; 
dp[1] =stairs[1]; 
if(n>=2) dp[2] = stairs[1] + stairs[2];
for (int i = 3; i<=n;i++){
	dp[i] = Math.max(
    	dp[i-2] + stairs[i], //2칸 점프 
        dp[i-3] + stairs[i-1] + stairs[i] //1칸씩 2번 
    );
}//for     

일반적이고 이해하기 쉽다. 단점은 배열 사용으로 메모리가 O(n)

Top-Down DP (재귀 + 메모이제이션)

static Integer[] dp; //null 체크 위해 Integer 사용 
public static void main(String[] args) {
	dp[0]= 0; 
    dp[1] = stairs[1]; 
    if(n>=2) dp[2]= stairs[1] + stairs[2]; 
    System.out.println(solve(n)); 
}//main

static int solve(int n){
	//이미 계산된것 건너뛰기 
    if(dp[n]!=null) return dp[n]; 
    
    dp[n]= Math.max(
    	solve(n-2) + stairs[n], 
        solve(n-3)+ stairs[n-1] + stairs[n]
    ); 
    return dp[n]; 
}//solve: 재귀 

2. 백준 1259 팰린드롬수

아이디어

• 처음에는 queue로 해서 앞에 있는것과 peek를 비교해서 양 옆을 제거하고 싶었으나 마지막에 들어온 것 제거하는 방법 모름 => //Deque 사용하면 양쪽 삽입 삭제 가능
• 그래서 그냥 배열로 받아 양쪽 비교하고, 안맞는 즉시 flag = false로 하고 바로 break함.

package boj_bronze.p1259_팰린드롬수;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
public static void main(String[] args)throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while(true){
String str = br.readLine();
//종료
if(str.equals("0")){
return;
}
//char로 바꾸기 !
Character[] chars = new Character[str.length()];
for (int i = 0; i < str.length(); i++) {
chars[i] = str.charAt(i);
}
int n = chars.length;
boolean flag = true;

        for(int i = 0; i< n; i++){
            if (chars[i]  != chars[n-i-1]){
                //하는 순간 바로 flag = false
                flag = false;
                break;
            }
        }
        if(flag){
            System.out.println("yes");
        }else{
            System.out.println("no");
        }



    }//while 입력 받기


}

}

** 내방법의 시간 복잡도와 공간 복잡도는 O(n)이다. 투 포인터로 사용하면 공간 복잡도는 O(1)로 효율적으로 구현할 수 있다. 추가 메모리 없이 charAt()만 사용한다. 
```java
//main 메서드 
while(true){
	String str = br.readLine(); 
    if(str.equals("0")) break; //0들어오면 바로 입력 종료 
    
    //함수 적용해서 팰린드롬수가 맞으면, yes 아니면 no출력한다. 
    sb.append(isPalindrom(str) ? "yes" :"no").append("\n");     
}//while 
//출력 
System.out.print(sb); 

//isPalindrom함수 
static boolean isPalindrome(String s){
	int l = 0; int r = s.length()-1; 
    
    while(l<r){
    	if(s.charAt(l++) !=s.charAt(r--)){
        	return false; 
        }
    }//whie
    return true; 
}