침대 밖은 위험해!

문제출처 : https://www.acmicpc.net/problem/2579

1. 문제요약

- 계단을 하나 건너 뛸 수 있음

- 최대 2번 연속으로만 밟을 수 있음

- 마지막 계단은 무조건 밟아야 함

- 1, 2, 4, 5 순으로 밟는건 가능

- 1, 2, 3, 4 순으로 밟는건 불가능 / 1, 2, 3 이 연속으로 3번 밟았기 때문

- 최대 합은?

2. 접근방법

- 방법 1.

  d[n] : n번째 계단에서 최대합

  현재 계단을 밟는 경우는 전전 계단을 밟고 한칸 뛰어서 현재 계단을 밟는 경우

                                  전 계단을 밟고 바로 연속으로 현재 계단을 밟는 경우

  하지만 전계단을 밟고 현재 계단을 밟는다면 현재를 n이라 했을 때, n-1번째 계단을 밟고 온 경우가

  n-1에서 두번 연속으로 밟은 경우인지 알 수 없음.

  그래서 n-3에서 최대합에서 n-2를 건너뛰고 n-1과 n 값을 합하면 됨

  d[n] = max(d[n-2] , d[n-3] + a[n-2]) + a[n]

- 방법 2.

  포도주 시식과 비슷한 방법으로

  d[3] : d[0] - 현재 계단을 밟지 않았을 때 최대합

          d[1] - 현재 계단이 연속 1회 일때 최대합

          d[2] - 현재 계단이 연속 2회 일때 최대합

  d[0] = max(d[1], d[2])

  d[1] = d[0] + a

  d[2] = d[1] + a

3. 시간복잡도

- 방법 1, 2 모두 n

4. 회고

- 포도주 시식 boj 2156 과 같은 문제

소스코드 방법 2

#include<iostream>
using namespace std;

int n, a, temp, d[3];

int max(int a, int b){
	return ((a < b) ? b : a);
}
int main(void){
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> a;
		temp = max(d[1], d[2]);
		d[2] = d[1] + a;
		d[1] = d[0] + a;
		d[0] = temp;
	}
	cout << max(d[1], d[2]) << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

문제출처 : https://www.acmicpc.net/problem/1912

1. 문제요약

- n개로 이루어진 임의의 수열 중 연속되는 숫자 합의 최대값은?

- A = {10, -4, 3, 1, 5, 6, -35, 12, 21, -1}

  A = {10, -4, 3, 1, 5, 6, -35, 12, 21, -1} 12 + 21 연속합이 33으로 최대

- 1 <= n <= 100,000

  -1,000 <= Ai <= 1,000

2. 접근방법

- 연속합이 최대

- 어느지점에서 새로운 연속이 생길까?

- 이전 까지의 합 보다 현재의 값이 더 크면 새로운 연속의 시작

- d[i] = max(d[i], d[i-1] + a[i])

3. 시간복잡도

- n

4. 회고

- 값의 범위가 -1000 <= Ai <= 1000 으로 음수가 됨을 망각함.

- 첫번째 실수, d의 값을 0으로 시작함..

  첫번째 입력값이 음수이면 d는 음수가 아니라 0으로 시작하게 됨

- 두번째 실수, ans의 값을 0으로 초기화함...

  집합의 모든 수가 음수 이면 정답은 0이 되어버림

소스코드

#include<iostream>
using namespace std;

int n, temp, d = -1001, ans = -1001;

int main(void){
	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> temp;
		if (temp < d + temp) d = d + temp;
		else d = temp;
		if (ans < d) ans = d;
	}
	cout << ans << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

문제출처 : https://www.acmicpc.net/problem/11054

1. 문제요약

- 수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... Sn-1 > Sn 을 만족한다면, 그 수열을 바이토닉 수열

- A = {1, 5, 2, 1, 4, 3, 4, 5, 2, 1}

  A = {1, 5, 2, 1, 4, 3, 4, 5, 2, 1} 가장 긴 바이토닉 수열의 길이는 7

2. 접근방법

- 좌측 LIS / 우측 LIS

3. 시간복잡도

- 2n^2 + n

4. 회고

소스코드

#include<iostream>
using namespace std;

int n, dl[1001], dr[1001], a[1001], ans;

int main(void){
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> a[i];
		dl[i] = 1;
		dr[i] = 1;
	}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < i; j++)
			if (a[i] > a[j] && dl[i] < dl[j] + 1)
				dl[i] = dl[j] + 1;
	for (int i = n - 1; i >= 0; i--)
		for (int j = n - 1; j > i; j--)
			if (a[i] > a[j] && dr[i] < dr[j] + 1)
				dr[i] = dr[j] + 1;
	for (int i = 0; i < n; i++)
		if (ans < dl[i] + dr[i]) ans = dl[i] + dr[i];
	cout << ans - 1 << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

문제출처 : https://www.acmicpc.net/problem/11722

1. 문제요약

- 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하라

- A = {10, 30, 10, 20, 20, 10}

  A = {10, 30, 10, 20, 20, 10} 가장 긴 감소하는 부분 수열의 최대 길이는 3

2. 접근방법

- LIS와 같음

3. 시간복잡도

- n^2

4. 회고

소스코드

#include<iostream>
using namespace std;

int n, d[1001], a[1001], ans = 0;

int main(void){
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < n; i++){
		d[i] = 1;
		for (int j = 0; j < i; j++)
			if (a[i] < a[j] && d[i] < d[j] + 1)
				d[i] = d[j] + 1;
		if (ans < d[i]) ans = d[i];
	}
	cout << ans << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

문제출처 : https://www.acmicpc.net/problem/11055

1. 문제요약

- 수열 A가 주어졌을 때, 수열의 증가 부분 수열 중 합이 가장 큰 것을 구하라

- A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8}

  A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 최대 합은 113

- 1 <= N <= 1,000

  1 <= Ai <= 1,000

2. 접근방법

- LIS와 같음

3. 시간복잡도

- n^2

4. 회고

소스코드

#include<iostream>
using namespace std;

int n, d[1001], a[1001], ans = 0;

int main(void){
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < n; i++){
		d[i] = a[i];
		for (int j = 0; j < i; j++)
			if (a[j] < a[i] && d[i] < d[j] + a[i])
				d[i] = d[j] + a[i];
		if (ans < d[i]) ans = d[i];
	}
	cout << ans << "\n";
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

문제출처 : https://www.acmicpc.net/problem/11053

1. 문제요약

- 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열은?

- A = {10, 20, 10, 30, 20, 50} 이면

  A = {10, 20, 10, 30, 20, 50} 으로 길이는 4가 된다

- 1 <= N <= 1,000

- 1 <= Ai <= 1,000

2. 접근방법

- Longest Increasing Subsequence

- 초기 값

- i = 1 / 0 <= j < i

  증가한다는 조건 이므로 a[i] > a[j]

  현재 행에서 증가하는 부분 수열의 길이는 d[i] = max(d[i], d[j] + 1)

- i = 2 / 0 <= j < i

- i = 3 / 0 <= j < i

- i = 4 / 0 <= j < i

- i = 5 / 0 <= j < i

3. 시간복잡도

- n^2

4. 회고

- nlogn 방법도 있음

- https://www.youtube.com/watch?v=S9oUiVYEq7E&feature=youtu.be

- http://stack07142.tistory.com/56

소스코드

#include<iostream>
using namespace std;

int n, d[1001], a[1001], ans = 0;

int main(void){
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < n; i++){
		d[i] = 1;
		for (int j = 0; j < i; j++){
			if (a[i] > a[j] && d[i] < d[j] + 1){
				d[i] = d[j] + 1;
			}
		}
		ans = (ans < d[i] ? d[i] : ans);
	}
	cout << ans << "\n";
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

문제출처 : https://www.acmicpc.net/problem/2156

1. 문제요약

- 일렬로 놓인 포도주 시식

- 선택하면 무조건 먹고 제자리

  연속 3잔을 마실 순 없음

- 포도주의 양이 주어졌을 때, 마실 수 있는 최대량?

- 1 <= n <= 10,000

- 1 <= 포도주 량 <= 1,000

2. 접근방법

- 일단 먹는다 안먹는다 뿐이니 다 해본다고 하면 2^10000...

- 현재 잔을 안먹는다.

  현재 잔을 먹었을 때 연속 1잔이다.

  현재 잔을 먹었을 때 연속 2잔이다.

  로 구분할 수 있음

- 나올 수 있는 경우의 수는

- d[0] : 현재 잔을 안마셨을 때 최대

  d[1] : 현재 잔을 마시면 연속 한잔 일때 최대

  d[2] : 현재 잔을 마시면 연속 두잔 일때 최대

- 현재 연속 0잔 d[0] = max(d[0], d[1], d[2])

  현재 연속 1잔 d[1] = d[0] + n번째 포도주 량

  현재 연속 2잔 d[2] = d[1] + n번째 포도주 량

3. 시간복잡도

- n

4. 회고

- d[10001][3] 으로 생각 했는데 그럴 필요가 없네

소스코드

#include<iostream>
using namespace std;

int n, a, temp, d[3];

int max(int a, int b){
	return ((a < b) ? b : a);
}

int main(void){
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> a;
		temp = max(d[0], max(d[1], d[2]));
		if (d[1]) d[2] = d[1] + a;
		d[1] = d[0] + a;
		d[0] = temp;
	}
	cout << max(d[0], max(d[1], d[2])) << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

문제출처 : https://www.acmicpc.net/problem/9465

1. 문제요약

- 2xn 스티커 배열

- 한장을 떼면 변을 공유하는 좌, 우, 상 또는 하 의 스티커는 못쓰게 됨

- 스티커당 점수가 있는데 뗀 스티커의 점수의 최대 합은?

- 1 <= n <= 100,000

2. 접근방법

- 브루트 포스로 접근하면, 2^100000 

  못품

- dp로 접근하면,

  : 회색 스티커를 뗀다면, 노란색 스티커 또는 초록색 스티커를 뗀 경우 최대가 된다

  : 각각 회색이 윗칸을 뗀경우, 아랫칸을 뗀 경우로 구분

3. 시간복잡도

- n

4. 회고

소스코드

#include<iostream>
using namespace std;

int t, n, d[2][100002];

int max(int a, int b){
	return ((a < b) ? b : a);
}

int main(void){
	cin >> t;
	while (t--){
		cin >> n;
		int a, b;
		for (int i = 0; i < 2; i++)
			for (int j = 1; j <= n; j++)
				cin >> d[i][j];
		for (int i = 2; i <= n; i++){
			d[0][i] += max(d[1][i - 1], d[1][i - 2]);
			d[1][i] += max(d[0][i - 1], d[0][i - 2]);
		}
		cout << max(d[0][n], d[1][n]) << "\n";
	}
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

문제출처 : https://www.acmicpc.net/problem/2193

1. 문제요약

- 0과 1로 이루어진 수 중에 0으로 시작하지 않고 1이 두번 연속으로 나타나지 않는 수를 이친수

- 1, 10, 101 등은 이친수

- 01, 110 은 이친수가 아님

- n자리 이친수의 갯수는?

- 1 <= n <= 90

2. 접근방법

- n자리 이진수를 브루트 포스로 다 확인할 수 없음.

- n자리가 0이면, n-1 자리는 0, 1

  n자리가 1이면, n-1 자리는 0

- d[n][i] 를 n자리수, 마지막 수가 i인 이친수의 갯수라고 하면

  d[n][0] = d[n-1][0] + d[n-1][1]

  d[n][1] = d[n-1][0]

- 조금만 더 생각을 해보면

- n자리가 0이면, n-1 자리는 0, 1

  n자리가 1이면, n-1 자리는 무조건 0 이므로 n-2 자리에 0, 1

- d[n] 을 n자리수 이친수의 갯수라고 하면

  d[n] = d[n-1] + d[n-2]

  피보나치

3. 시간복잡도

- n

4. 회고

- 이친수의 갯수가 int형을 넘을 수 있으므로 long long

소스코드

#include<iostream>
using namespace std;

int n;
long long d[100] = { 0, 1 };

int main(void){
	cin >> n;
	for (int i = 2; i <= n; i++){
		d[i] = d[i - 1] + d[i - 2];
	}
	cout << d[n] << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

문제출처 : https://www.acmicpc.net/problem/11057

1. 문제요약

- 33455, 012345와 같이 각 자릿수가 오름차순인 수를 오르막 수라 함.

- 인접한 수가 같아도 오름차순으로 인정

- 9111 과 같은 수는 오르막 수가 아님

- 수는 0으로 시작 할 수 있음

- 오르막 수의 갯수는?

- 1 <= n <= 1,000

2. 접근방법

- n자릿수가 1000 이므로 모든 수를 다 확인 할 수 없음

- n 자릿수의 마지막 수가 0 이면, n-1 자릿수의 마지막 수는 0

  n 자릿수의 마지막 수가 1 이면, n-1 자릿수의 마지막 수는 0, 1

  n 자릿수의 마지막 수가 2 이면, n-1 자릿수의 마지막 수는 0, 1, 2

  ...

- 필요한 항목은 자릿수, 마지막 수 이므로

- d[n][j] : n 자릿수, 마지막 수가 j인 오르막 수의 갯수

- d[n][j] = d[n-1][0] + d[n-1][1] + ... + d[n-1][j-1] + d[n-1][j] = ∑(i=0, j) d[n-1][i]

3. 시간복잡도

- n

4. 회고

- 10007의 나머지 이므로 n이 1000 이라 해도 1000자릿수의 10007의 나머지 합이 int 범위를 넘어 갈 수 없음

소스코드

#include<iostream>
using namespace std;

int n, d[1001][10], ans = 0;

int main(void){
	cin >> n;
	for (int i = 0; i < 10; i++) d[1][i] = 1;
	for (int i = 2; i <= n; i++){
		for (int j = 0; j < 10; j++){
			for (int k = 0; k <= j; k++){
				d[i][j] += d[i - 1][k];
			}
			d[i][j] %= 10007;
		}
	}
	for (int i = 0; i < 10; i++) ans += d[n][i];
	cout << ans % 10007 << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]