#include <iostream>
#include <algorithm>
using namespace std;
int d[1000];
int a[1000];
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
for (int i = 0; i < N; i++)
cin >> a[i];
d[0] = 1;
for (int i = 1; i < N; i++) {
d[i] = 1;
for (int j = 0; j < i; j++) {
if (a[j] < a[i])
d[i] = max(d[i], d[j] + 1);
}
}
cout << *max_element(d, d + N);
return 0;
}
5번 라인 : 다이나믹 프로그래밍으로 문제를 풀기 위해 길이가 수열의 크기의 최댓값(1000)인 배열을 선언했습니다. d[i]에는 i번째 수열의 항을 마지막으로 포함하는 부분 수열의 길이의 최댓값을 저장합니다.
6번 라인 : 수열의 각 항의 값을 입력받기 길이가 1000인 배열을 선언했습니다.
16번 라인 : 수열의 각 항의 값을 입력받아 배열 a에 저장합니다.
18번 라인 : d[0]은 0번째 항을 마지막으로 포함하는 부분 수열의 길이의 최댓값이므로 {a[0]}을 의미합니다. 따라서 1을 저장합니다.
19번 라인 : i = 1부터 N - 1까지 for문을 돌 때
20번 라인 : d[i]의 최솟값은 {a[i]}로 길이가 1이므로 일단 1로 초기화합니다.
21번 라인 : d[i]는 i번째 항을 마지막으로 포함하는 부분 수열의 길이의 최댓값이므로 for문을 이용해 j = 0부터 j < i까지 돌면서,
22번 라인 : j번째 수열의 항이 i번째 수열의 항보다 작다면 (예를 들어, a = {10, 30, 20}이고 i = 2라면 j = 0일 때는 10(a[j]) < 20(a[i])이므로 증가하는 부분 수열이 성립하지만, j = 1일 때는 30(a[j]) < 20(a[i])가 성립하지 않으므로 증가하는 부분 수열이 될 수 없습니다.)
23번 라인 : d[i]는 현재까지 i번째 항을 마지막으로 포함하는 부분 수열의 길이의 최댓값(d[i])과, j번째 항을 마지막으로 포함하는 부분 수열의 길이의 최댓값(d[j])에 i번째 항을 추가한 값인 d[j] + 1 중에서 큰 값을 d[i]에 저장합니다.
26번 라인 : d[0] ~ d[N - 1]까지의 값 중에서 최댓값을 출력하면 되고, 이를 구하기 위해 max_element함수를 사용했습니다.
계단의 개수와 각 계단의 점수를 입력받아, 계단 오르기 게임에서 얻을 수 있는 총점수의 최댓값을 출력하는 문제입니다.
계단 오르기 게임의 규칙은 다음과 같습니다.
1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.
다이나믹 프로그래밍으로 풀 수 있는 문제입니다.
3. 소스코드
BOJ 2579번 계단 오르기 C++ 풀이입니다.
#include <iostream>
#include <algorithm>
using namespace std;
int d[300][2];
int step[300];
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> step[i];
d[0][0] = step[0];
d[1][0] = step[1];
d[1][1] = step[0] + step[1];
for (int i = 2; i < n; i++) {
d[i][0] = max(d[i - 2][0], d[i - 2][1]) + step[i];
d[i][1] = d[i - 1][0] + step[i];
}
cout << max(d[n - 1][0], d[n - 1][1]);
return 0;
}
5번 라인 : 다이나믹 프로그래밍으로 문제를 풀기 위해 계단의 개수의 최댓값인 300크기의 int형 배열을 선언합니다. 계단 오르기 게임의 규칙이 한 번에 한 계단씩 또는 두 계단씩 오를 수 있고, 연속된 세 개의 계단을 모두 밟아서는 안 되므로, 이 조건을 검사하기 위해 d[i][0]에는 계단을 연속해서 밟지 않는 경우(즉, i -2번째 계단을 밟은 후 i번째 계단을 밟는 경우)의 최대 점수값을 저장하고, d[i][1]에는 계단을 연속해서 밟는 경우(즉, i - 1번째 계단을 밟은 후, i번째 계단을 밟는 경우)의 최대 점수 값을 저장합니다.
6번 라인 : 각 계단의 점수를 저장할 step 배열을 선언합니다. 역시 계단의 개수의 최댓값이 300이므로 크기는 300으로 선언했습니다. d배열과 step배열 모두 0으로 초기화하기 위해 전역변수로 선언했습니다.
16번 라인 : 각 계단의 점수를 입력받아 step배열에 저장합니다. 문제에서는 1번째부터 시작하지만 편의를 위해 0번째부터 저장했습니다.
18번 라인 : 0번째 계단은 연속해서 밟을 수 없으므로 d[0][0]만 가능하므로 d[0][0]에 0번째 계단의 점수를 저장합니다.
19번 라인 : 1번째 계단은 연속해서 밟지 않는 경우 바로 1번째 계단을 밟는 것이기 때문에 d[1][0]에 1번째 계단의 점수를 저장합니다.
20번 라인 : 1번째 계단은 연속해서 밟는 경우, 0번째 계단, 1번째 계단을 밟는 것이기 때문에 d[1][1]에 0번째 계단의 점수와 1번째 계단의 점수의 합을 저장합니다.
21번 라인 : 2번째 계단부터 n - 1번째 계단까지 for문을 돌면서
22번 라인 : d[i][0]번째 계단에는 계단을 연속해서 밟지 않는 경우를 저장하기 때문에, i-2번째 계단을 밟은 후, i번째 계단을 밟는 경우입니다. 따라서 i-2번째 계단을 밟을 때 얻을 수 있는 점수인 d[i - 2][0]과 d[i - 2][1] 중에서 큰 값과 i번째 계단의 값을 더해서 저장합니다.
23번 라인 : d[i][1]번째 계단에는 계단을 연속해서 밟는 경우를 저장하기 때문에 i-1번째 계단을 밟은 후, i번째 계단을 밟는 경우입니다. 연속된 세 개의 계단을 밟을 수 없으므로 d[i - 1][1]을 선택할 수 없습니다. 따라서 d[i - 1][0]에 저장된 점수에 i번째 계단의 값을 더해서 저장합니다.
25번 라인 : 계단의 점수를 입력받을 때 0번째 부터 입력받았으므로, 최종적으로 n - 1번째 계단을 밟았을 때의 점수 중에서 큰 값을 출력합니다.
2. 화살표 case 라벨, 다중 case 라벨 (switch1, enhancedSwitch1)
switch (day) {
case MONDAY:
case FRIDAY:
case SUNDAY:
System.out.println(6);
break;
case TUESDAY:
System.out.println(7);
break;
case THURSDAY:
case SATURDAY:
System.out.println(8);
break;
case WEDNESDAY:
System.out.println(9);
break;
}
day의 길이를 출력하는 기존 switch 문 예제입니다.
day가 MONDAY, FRIDAY, SUNDAY인 경우 fall through를 이용하여 6을 출력하는 것을 볼 수 있습니다.
이를 화살표 case 라벨과 다중 case 라벨을 사용한 개선된 switch문으로 바꾸면 아래와 같습니다.
switch (day) {
case MONDAY, FRIDAY, SUNDAY -> System.out.println(6);
case TUESDAY -> System.out.println(7);
case THURSDAY, SATURDAY -> System.out.println(8);
case WEDNESDAY -> System.out.println(9);
}
fall through를 사용하지 않고 다중 case 라벨(,)을 사용하여 case MONDAY, FRIDAY, SUNDAY라고 표현한 것이 훨씬 가독성이 좋습니다.
또, 화살표 case 라벨(->)을 사용하면 마지막에 break를 사용한 것과 동일합니다.
이때 주의해야 할 점은 case 라벨(:)을 사용할 때는 실행문이 여러 개여도 중괄호({})로 묶어줄 필요가 없었지만,
화살표 case 라벨(->)을 사용할 때 실행문이 여러 개(즉, 2줄 이상)일 때는 중괄호로 묶어줘야 합니다.
한마디로 화살표 case 라벨(->)을 사용할 때는 if 문이나 for 문처럼 실행문이 1줄일 때만 중괄호를 생략할 수 있습니다.
3. switch 연산식 (switch2, enhancedSwitch2)
int numLetters;
switch (day) {
case MONDAY:
case FRIDAY:
case SUNDAY:
numLetters = 6;
break;
case TUESDAY:
numLetters = 7;
break;
case THURSDAY:
case SATURDAY:
numLetters = 8;
break;
case WEDNESDAY:
numLetters = 9;
break;
default:
numLetters = -1;
}
numLetters 변수에 day의 길이를 저장하는 기존 switch 문 예제입니다.
case 문에서 numLetters 변수에 값을 저장하는 방식을 사용해야 합니다.
이를 switch 연산식을 사용한 향상된 switch 문으로 바꾸면 아래와 같습니다.
int numLetters = switch (day) {
case MONDAY, FRIDAY, SUNDAY -> 6;
case TUESDAY -> 7;
case THURSDAY, SATURDAY -> 8;
case WEDNESDAY -> 9;
};
화살표 case 라벨(->) 뒤에 있는 값을 return하여 numLetters에 바로 대입할 수 있습니다.
만약 case TUESDAY -> 7;에서 7을 System.out.println(7)이나 "Seven" 등으로 바꾸면 int type이 아니므로 에러가 발생합니다.
numLetters의 type을 Object로 바꿔주면 "Seven"은 가능하지만,
System.out.println(7)은 return type이 void이므로 여전히 에러가 발생합니다.
즉, switch 연산식을 사용할 때 화살표 case 라벨(->) 뒤에 있는 값이 void type이면 에러가 발생합니다.
4. yield 예약어 사용 (enhancedSwitch3, enhancedSwitch4)
yield는 키워드가 아니라 제한된 식별자(restricted identifier)이기 때문에 var처럼 식별자로 사용할 수 있습니다.
방금 전에 본 switch 연산식에서 길이를 return하기 전에 특정 메시지를 출력하고 싶으면 아래와 같이 사용하면 됩니다.
int numLetters = switch (day) {
case MONDAY, FRIDAY, SUNDAY -> {
System.out.print("Six ");
yield 6;
}
case TUESDAY -> 7;
case THURSDAY, SATURDAY -> 8;
case WEDNESDAY -> 9;
};
향상된 switch 문에서는 중괄호 안에서만 yield 예약어를 사용할 수 있습니다.
따라서 case TUESDAY -> yield 7; 이라고 하면 에러입니다.
int numLetters = switch (day) {
case MONDAY, FRIDAY, SUNDAY:
System.out.print("Six ");
yield 6;
case TUESDAY:
yield 7;
case THURSDAY, SATURDAY:
yield 8;
case WEDNESDAY:
yield 9;
};
yield 예약어는 case 라벨(:)에도 사용 가능합니다.
case 라벨(:)은 실행문이 여러 개일 때 중괄호를 사용하지 않아도 됩니다.
5. 열거 타입(enum)을 사용하는 이유
static int switchError(String s) {
return switch (s) {
case "MONDAY", "FRIDAY", "SUNDAY" -> 6;
case "TUESDAY" -> 7;
case "THURSDAY, SATURDAY" -> 8;
case "WEDNESDAY" -> 9;
default -> -1;
};
}
위의 메서드에서 default를 주석 처리하면 "'switch' expression does not cover all possible input values" 에러 메시지를 볼 수 있습니다.
가능한 모든 값에 대하여 일치하는 case 라벨이 하나라도 없으면 위와 같은 에러를 볼 수 있습니다.
위의 예제에서는 String type이므로 가능한 모든 값은 거의 무한대나 마찬가지입니다.
String대신 int type이고, default를 사용하지 않는다면 int 범위의 모든 값에 대하여 case를 사용해야 할 것입니다.
따라서 default를 사용하거나, 필요한 값들로 열거 타입(enum)을 만들어서 사용해야 합니다.