(2020년 10월 4일에 작성한 글입니다.)
학회 코드포스 스터디에서 버추얼로 풀었다.
A.
일단 'subarray'의 정의를 잘못 파악해서 처음에 틀렸다...
delete several elements from the beginning and from the end인데
sequence처럼 중간에 빼서 합쳐도 되는 줄
여튼 그거 때문에 처음에는
sum을 구해놓고 X로 나누어떨어지는지 확인해서
만약 안 나누어 떨어지면 N이 답이고
나누어 떨어지면, X의 배수가 아닌 수가 있는지 확인하고
만약에 있으면 N-1, 없으면 -1을 출력하는 방식으로 했는데
틀려서
subarray의 정의를 다시 체크한 다음에
input을 받을때부터 X의 배수가 아닌 수의 인덱스를 vector에 저장해놓고
sum이 X의 배수가 아니면 N 출력,
X의 배수이면, vector의 크기가 0이면 -1 출력,
아니면 앞, 뒤를 제거해서 subarray를 만들었을 때 더 긴 것을 출력
이런 식으로 했다.
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
int N, X;
int sum;
int temp;
bool flag;
int i;
cin >> T;
while (T--) {
cin >> N >> X;
flag = false;
sum = 0;
vector<int> index;
for (i = 0; i < N; i++) {
cin >> temp;
sum += temp;
if (temp % X != 0) {
flag = true;
index.push_back(i);
}
}
if (sum % X == 0) {
if (flag) {
cout << max(N - index.front() - 1, index.back()) << '\n';
}
else {
cout << -1 << '\n';
}
}
else {
cout << N << '\n';
}
}
return 0;
}
B.
이것도 처음에 생각을 이상하게 해서 틀렸다.
만약에 연속적으로 증가하거나 감소하는 부분이 있으면
가장 첫 수와 마지막 수만 남겨놓고 나머지는 다 없애면 된다.
한 마디로 극대/극소 지점만 남겨놓으면 된다.
근데 이걸 처음엔 이상하게 풀었다..
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
int N;
int i;
cin >> T;
while (T--) {
cin >> N;
vector<int> arr(N);
for (i = 0; i < N; i++) {
cin >> arr[i];
}
vector<int> ans;
ans.push_back(arr[0]);
for (i = 0; i < N - 1;) { //i 종료조건 뭐야?
if (arr[i] < arr[i + 1]) {
for (; i < N - 1 && arr[i] < arr[i + 1]; i++);
}
else {
for (; i < N - 1 && arr[i] > arr[i + 1]; i++);
}
ans.push_back(arr[i]);
}
cout << ans.size() << '\n';
for (i = 0; i < ans.size(); i++) {
cout << ans[i] << ' ';
}
cout << '\n';
}
return 0;
}