[백준BaekJoon]21318: 피아노 체조/C++

문제

피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 N개의 악보를 가지고 있으며, 1번부터 N번까지의 번호로 부른다. 각 악보는 1 이상 109 이하의 정수로 표현되는 난이도를 가지고 있다. 난이도를 나타내는 수가 클수록 어려운 악보이다. 1 ≤ x ≤ y ≤ N 을 만족하는 두 정수 x, y를 골라 x번부터 y번까지의 악보를 번호 순서대로 연주하는 것이 피아노 체조이다.

시은이는 피아노 체조를 할 때, 지금 연주하는 악보가 바로 다음에 연주할 악보보다 어렵다면 실수를 한다. 다시 말하자면, i(x ≤ i < y)번 악보의 난이도가 i + 1번 악보의 난이도보다 높다면 실수를 한다. 특히, 마지막으로 연주하는 y번 악보에선 절대 실수하지 않는다. 시은이는 오늘도 피아노 체조를 하기 위해 두 정수 x와 y를 골랐고, 문득 궁금한 것이 생겼다. 오늘 할 피아노 체조에서 실수하는 곡은 몇 개나 될까?

---

코드

시간 제한을 보고 안될 걸 알면서도 이중for문으로 일단 건드려 봤다.

#include <bits/stdc++.h> 
using namespace std;
int arr[100000];

int main() {    
	int N, Q;
	cin >> N;
	for (int i = 0; i < N; i++)cin >> arr[i];

	cin >> Q;
	while (Q--) {
		int x, y, ans = 0;
		cin >> x >> y;
		
		for (int i = x - 1; i < y - 1; i++) {
			if (arr[i] > arr[i + 1])ans++;
		}

		cout << ans << "\n";
	}
}

될 리가 없지 ㅎㅎ....

 

구간이 나뉘어져 있으니 악보를 연주할 때마다 실수한 횟수(현재 난이도가 다음 악보의 난이도보다 높을 경우)를 누적해주고, 구해야할 구간까지의 횟수에서 이전 구간의 횟수를 빼주었다.

이때 y번째는 무조건 성공한다 하였으니 y-1번째 구간까지를 계산해주었다.

#include <bits/stdc++.h> 
using namespace std;

int arr[100001], sum[100001];

int main() {
	int N, Q;
	cin >> N;
	arr[0] = 0, sum[0] = 0;
	for(int i = 1; i <= N; i++) cin >> arr[i];

	for (int i = 1; i < N; i++) {
		if (arr[i] > arr[i + 1]) {
			sum[i] = sum[i - 1] + 1;
		}
		else {
			sum[i] = sum[i - 1];
		}
	}	
	sum[N] = sum[N-1];
	
	cin >> Q;
	while (Q--) {
		int x, y;
		cin >> x >> y;
		
		cout << sum[y-1] - sum[x-1] << "\n";
	}
}

문제에 나온 예제 입력1의 경우

sum[1]부터 sum[9]까지의 값은 0 0 0 0 1 1 2 3 3 이다. 마지막 악보같은 경우는 사실상 쓰이지 고려해주지 않아도 되지만...

 

4번부터 7번까지 실수 횟수를 구하고 싶으면, 7번은 무조건 성공하니 1번부터 6번까지의 횟수에서 1번부터 3번까지의 횟수를 빼주면 된다.

6번부터 9번까지 실수 횟수를 구하고 싶은 경우, 마찬가지로 1번부터 8번까지의 횟수에서 1번부터 5번까지의 횟수를 빼준다. 9번까지 총 3번 실수를 했는데, 5번까지는 1번 실수했으니 6번부터 9번까지는 2번 실수한 셈이다.

 

끝. 구간이 정해져 있으면 이제는 이중 for문보다는 어떤 값들을 누적시킬지 먼저 떠올려야겠다.

DP와도 연관있어 보인다.

.

.

.

?

정신나가는줄 알았다 ㅋㅋㅋ,,,

1%에서 시간 초과 뜨길래 변수나 배열 선언을 잘못했나 싶어서 구글링을 열심히 했지만 코드에는 전혀 문제가 없어보였다...

뭘까 싶어서 생각해보니

 

	ios::sync_with_stdio(0);
	cin.tie(0);

이 귀여운 친구들을 빼먹었다...

평소에 main 함수 비롯해서 기본 틀은 복붙해서 썼는데, 코딩하는 환경이 바뀌면서 같이 날려버렸다ㅋㅋㅋㅋ..

 

ios::sync_with_stdio(0);

c의 stdio와 c++의 iostream의 동기화를 비활성화시켜준다. c++은 독립적인 버퍼를 사용하게 되어 연산 속도가 향상된다.

 

cin.tie(0);

cin과 cout 입출력 묶음을 풀어주면서 시간을 단축시킨다.

 

입출력 속도에 관해서는 나중에 다시 자세히 공부해서 적어야겠다 ㅎ...

진짜 끝.