백준] 9461 : 파도반 수열

BOJ에서 다음 문제들을 쭉 순서대로 풀어본다.  boj.kr/문제번호 <= 형태로 검색하면 된다.

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

 

 

1시간 넘어가면 풀던 짓을 그만두고 반드시 AC받은 코드 찾아보기 (설명이 꼭 달려있는 코드를 읽자)

그리고 푼 다음에는 반드시 다른 사람의 코드를 봐야 한다.

특히 자신만의 가상의 스승을 잡고 그 분의 코드를 보는 것도 좋은 방법이라 생각한다.

너무 갓갓들은 이상한 방식으로도 짜는 경우도 있기 때문에 적당한 사람을 선택해야 한다.

 

알고리즘 문제풀이(PS) 시작하기

 

내가 애용하는 IDE 사이트

(IDE 자동 완성이 불가능하기 때문에 사용하는 중)

Ideone.com

---

 

9461번: 파도반 수열

 

 

접근 방법

 

 위 그림과 같은 방식으로 규칙을 찾았습니다.

①..은 각 숫자의 index입니다.

규칙을 찾다보니 dp[i] = dp[i - 3] + dp[i - 2] 라는 반복을 찾을 수 있었습니다.

 

🌱 정답 코드

#include <iostream>
using namespace std;

long long dp[101], T, N;
// ** 메모리를 위해 long long으로 지정해주기

int main() {
	
	cin >> T;
	
	 dp[1] = 1;
	 dp[2] = 1;		
	 dp[3] = 1;
	 dp[4] = 2;
				
	for(int i = 1; i <= T; i++){
		cin >> N;
	
		for(int j = 5; j <= N; j++){
			dp[j] = dp[j - 3] + dp[j - 2]; 
		}
		cout << dp[N] << endl;
	}
	
	return 0;
}

 

 

 

#include <iostream>
using namespace std;

int dp[101], arr[101], T;

int main() {
	
	cin >> T;
	
	dp[1] = 1;
	dp[2] = 1;
	dp[3] = 1;

	for(int i = 1; i <= T; i++){
		cin >> arr[i];
	}
	
	for(int i = 4; i <= arr[T]; i++){
		dp[i] = dp[i - 2] + dp[i - 3]; 
	}
	
	for(int i = 1; i <= T; i++){
		cout << dp[arr[i]] << endl;
	}

	return 0;
}

>> 비효율적으로 짜서 틀렸다.. ㅎ