nn개의 숫자들로 이루어진 두 개의 수열 a=a1 a2⋯ana=a1 a2⋯an와 b=b1 b2⋯bnb=b1 b2⋯bn가 있다.
두 수열 aa와 bb의 유사도란 두 수열에서 같은 위치의 숫자가 일치하는 개수이다.
예를 들어, a=5 2 3 7 6 1a=5 2 3 7 6 1와 b=5 7 1 2 6 3b=5 7 1 2 6 3가 주어지면, 제일 첫 번째 숫자 5와 뒤에서 두 번째 숫자 6이 일치하므로 aa와 bb의 유사도는 2이다.
우리는 두 번째 수열 bb에 대해서만 임의의 구간 [i,j][i,j]를 선택해서 이 구간에 속한 수들을 회전시킨다.
여기서, 회전이라는 것은 이 구간에 속한 수 bi bi+1⋯bj−1 bjbi bi+1⋯bj−1 bj를 bj bj−1⋯bi+1 bibj bj−1⋯bi+1 bi와 같이 앞쪽과 뒤쪽의 수들을 서로 맞 바꾸는 것이다.
특별한 경우로 구간 [i,i][i,i]을 회전하면 수열엔 변화가 없다.
위 예의 b=5 7 1 2 6 3b=5 7 1 2 6 3에서 구간 [3,6][3,6]을 회전하면, bb는 수열 5 7 3 6 2 15 7 3 6 2 1이 되고 두 수열의 유사도는 3이 된다.
그러나 bb 에서 구간 [2,4][2,4]를 회전하면, bb는 수열 5 2 1 7 6 35 2 1 7 6 3 이 되고 두 수열의 유사도는 4 가 된다.
두 수열 aa와 bb가 주어질 때, 수열 bb의 구간을 선택해서 단 한번 회전한 후 두 수열의 유사도가 최대가 되도록 하고 그 때의 유사도를 출력하는 프로그램을 작성하시오.
- 제한시간: 전체 테스트 케이스는 40개 이하이며, 전체 수행 시간은 2초 이내. (Java 4초 이내)
제한 시간을 초과하면 제출한 소스코드의 프로그램이 즉시 종료되며,
그때까지 수행한 결과에서 테스트 케이스를 1개 그룹 이상 통과하였더라도 점수는 0점이 됩니다.
그러나, 제한 시간을 초과하더라도 테스트 케이스를 1개 그룹 이상 통과하였다면 '부분 점수(0< 점수< 만점)'를 받을 수 있으며,
이를 위해서는, C / C++ 에서 "printf 함수" 사용할 경우, 프로그램 시작부분에서 "setbuf(stdout, NULL);"를 한번만 사용하십시오.
C++에서는 "setbuf(stdout, NULL);"와 "printf 함수" 대신 "cout"를 사용하고, Java에서는 "System.out.printIn"을 사용하시면,
제한 시간을 초과하더라도 '부분 점수'를 받을 수 있습니다.
※ 언어별 기본 제공 소스코드 내용 참고
만약, 제한 시간을 초과하지 않았는데도 '부분 점수'를 받았다면, 일부 테스트 케이스를 통과하지 못한 경우 입니다.
- 메모리 사용 제한 : heap, global, static 총계 256MB, stack 100MB
- 제출 제한 : 최대 10회 (제출 횟수를 반영하여 순위 결정 → 동점자의 경우 제출 횟수가 적은 사람에게 높은 순위 부여)
메모리 사용 제한
heap, global, static (총계) : 256MB
stack : 100MB
입력
입력 파일에는 여러 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 TT 가 주어지고,
이후 차례로 TT개의 테스트 케이스가 주어진다. (1≤T≤40)(1≤T≤40)
각 테스트 케이스의 첫 줄에는 두 수열을 이루는 숫자들의 개수 nn이 주어진다. nn의 범위는 1 이상 5,000 이하이다.
둘째 줄에는 첫 번째 수열 aa를 나타내는 nn개의 숫자들이 주어진다. 셋째 줄에는 두 번째 수열 bb를 나타내는 nn개의 숫자들이 주어진다.
여기서, 두 수열을 이루는 숫자들은 1이상 106106이하의 정수이다.
- 점수 : 각 제출에서 취득한 점수 중에서 최대 점수 (만점 150점)
주어지는 테스트 케이스 데이터들의 그룹은 아래와 같으며,
각 그룹의 테스트 케이스를 모두 맞추었을 때 해당되는 부분 점수를 받을 수 있다.
ㆍ 그룹 1 (24점) : 이 그룹의 테스트 케이스에서는 n≤50n≤50 이다.
ㆍ 그룹 2 (36점) : 이 그룹의 테스트 케이스에서는 n≤500n≤500 이다.
ㆍ 그룹 3 (90점) : 이 그룹의 테스트 케이스에서는 원래의 조건 외에는 다른 제약조건이 없다.
출력
각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,
각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 C는 테스트 케이스의 번호이다.
그 다음 줄에, 수열 bb의 구간을 단 한번 회전했을 때, 두 수열 유사도의 최대값을 출력한다.
출처
SCPC 2019 Round2
나의 답
#include <iostream>
#include <vector>
using namespace std;
int Answer;
int max_Answer;
int end_num;
vector<int> array1;
vector<int> array2;
int same_num(int A, int B) {
int result = 0;
if(array1[A]==array2[A])
result--;
if(array1[B]==array2[B])
result--;
if(array1[A]==array2[B])
result++;
if(array1[B]==array2[A])
result++;
return result;
}
void calc(int Axis) {
int cur_Answer = Answer;
int distance = 1;
int left_Axis = Axis;
if(Axis%2==1)
left_Axis++;
while((left_Axis-(distance*2))/2>-1&&(Axis+(distance*2))/2<=end_num) {
cur_Answer += same_num((left_Axis-(distance*2))/2, (Axis+(distance*2))/2);
max_Answer = max(max_Answer, cur_Answer);
distance++;
}
if(Axis+1<end_num*2)
calc(Axis+1);
}
int main(int argc, char** argv)
{
int T, test_case;
cin >> T;
for(test_case = 0; test_case < T; test_case++)
{
Answer = 0;
// input array
int vari_num;
cin >>vari_num;
array1.resize(vari_num);
array2.resize(vari_num);
for(int i = 0; i < vari_num; ++i) {
cin >> array1[i];
}
for(int i = 0; i < vari_num; ++i) {
cin >> array2[i];
}
end_num = vari_num-1;
for(int i = 0; i <= end_num; ++i) {
if(array1[i]==array2[i])
Answer++;
}
max_Answer = Answer;
calc(1);
array1.clear();
array2.clear();
cout << "Case #" << test_case+1 << endl;
cout << max_Answer << endl;
}
return 0;
}해설
array1과 array2에 배열 2개를 할당받는다. 그리고 아무것도 바꾸지 않았을 때의 정답을 Answer 변수에 저장한다. 그리고 각 숫자와 숫자 사이사이를 축으로 해서 반대로 뒤집어서 계산을 수행한다. 이 때, calc에 들어가는 변수는 그 축이 되는 지점이며, distance는 축과 바꿀 숫자들 사이의 거리이다. 그런 식으로 축을 기준으로 하나씩 뒤집어서 정답을 갱신한다. 이 때, same_num은 A와 B자리를 바꿀 때, 기존 답에서 얼마만큼이 변경되는지를 계산해주는 함수이며, 기존에 A나 B자리의 수가 같을 때는 -1을 해주고 바꿨을 때 수가 같으면 +1을 해준다. 이렇게 나온 값을 기존 정답에 더해준다.
'CodeGround' 카테고리의 다른 글
| [98번] 소수 수열 (0) | 2020.08.13 |
|---|