https://www.acmicpc.net/problem/1744
1744번: 수 묶기
길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에
www.acmicpc.net
난이도: solved.ac 골드 4
분명히 내가 사용하는 visual studio로는 예제에 나온 input이나
질문 게시판에 나온 반례들을 모두 만족하길래
도대체 어디가 틀렸는지 화가 났던 문제다
그래서 알고리즘 톡방에 질문을 올렸는데
아주 고마운 분께서 정성스럽게 답변을 해주셨다...
내가 빠트렸던 부분(잘 몰라서...) 은 맨 아래에서 설명하겠다
일단 내 풀이 방식은 이렇다
[풀이 방식]
일단, input에서 1과 0은 특이 케이스로 분류한다.
그리고 수열을 오름차순으로 정렬한다
그 후 단계는 아래와 같다
(1차 단계)
1. 음수가 홀수 개일 때
- 크기가 작은 것부터 2개씩 쌍을 지어 곱하고 더함
- 남은 하나는 아래의 경우에 따라 계산
1) 수열에 0이 있을 때: 남은 하나와 0을 묶어 곱하고 더함
2) 0이 없을 때: 어쩔 수 없이 그냥 더함
2. 음수가 짝수 개일 때
- 크기가 작은 것부터 2개씩 쌍을 지어 곱하고 더함
3. 음수가 하나도 없을 때: 다음 단계로 넘어감
(2차 단계)
1. '1보다 큰 양수'가 홀수 개일 때
- 크기가 큰 것부터 2개씩 쌍을 지어 곱하고 더함
- 남은 하나는 그냥 더함
2. '보다 큰 양수'가 짝수 개일 때
- 크기가 큰 것부터 2개씩 쌍을 지어 곱하고 더함
(3차 단계)
1. 연산에 포함하지 않은 수는 0 또는 1밖에 없음
- 1차 단계 1번에서 0이 있는 경우 제외하고
2. 남은 0과 1은 모두 그냥 더해줌
(코드)
길어보이는데 주석빼면 얼마 안된다...
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
int compare(int* a, int* b) {
return *a - *b;
}
int main() {
int N, i; // i: index로 사용
scanf("%d", &N);
int* arr = (int*)malloc(sizeof(int) * N);
int negative = 0, positive = 0;
// negative: 음수의 개수, positive: 1보다 큰 양수의 개수
int sum = 0;
for (i = 0; i < N; i++){
scanf("%d", &arr[i]);
if (arr[i] < 0)
negative++;
else if (arr[i] > 1)
positive++;
}
qsort(arr, N, sizeof(int), compare); // 오름차순 정렬
/*
여기서는 짝을 지어 더해주는 과정이 끝나고 남은 0과 1을(1보다 큰 양수가 홀수 개인 경우는 0, 1, 남은 양수 하나)
더해주는 과정을 단순화하기 위해서
arr[i] * arr[i+1]로 2개씩 짝을 지어 곱하여 sum에 더해준 뒤,
arr[i]과 arr[i+1]의 값을 0으로 바꿔줬음
(for문으로 arr[0]부터 arr[N-1]까지 더해주는 방식으로 하려고)
*/
/* 음수 부분 */
i = 0; // i를 0으로 초기화
if (negative % 2 == 1) { // 음수가 홀수 개일 때
while (i < negative - 1) { // 두 개씩 쌍을 짓고 남은 하나를 만들기 위해 'negative - 1'
sum += arr[i] * arr[i + 1];
arr[i] = 0; // sum에 더한 후 arr[i]과 arr[i+1]을 0으로 바꿔줌
arr[i + 1] = 0;
i += 2; // 두 칸 뒤로
}
// 위의 과정을 거치고 남은 음수 다음의 원소가 0이면, 0과 짝을 지어 곱해 더해야 sum이 최대가 됨
if (arr[i + 1] == 0 && N - 1 == i); // input: -3 -2 -1처럼 input에 음수만 있는 경우
else if (arr[i + 1] == 0) // 남은 음수 다음의 원소가 0일 때
arr[i] = 0; // 0과 곱한다 치고 값을 0으로 바꿔줌
}
else if (negative != 0) { // 음수가 짝수 개일 때
while (i < negative) {
sum += arr[i] * arr[i + 1];
arr[i] = 0; // 마찬가지로 sum에 더한 후 arr[i]과 arr[i+1]을 0으로 바꿔줌
arr[i + 1] = 0;
i += 2; // 두 칸 뒤로
}
}
/* 양수 부분 */
i = 0; // i를 0으로 초기화
if (positive % 2 == 1) { // 1보다 큰 양수가 홀수 개일 때
while (i < positive - 1) { // 두 개씩 쌍을 짓고 남은 하나를 만들기 위해 'negative - 1'
sum += arr[N - i - 1] * arr[N - i - 2]; // 큰 값부터 2개씩 쌍을 지음
arr[N - i - 1] = 0; // 마찬가지로 sum에 포함시킨 뒤 0으로 바꿔줌
arr[N - i - 2] = 0;
i += 2;
}
// 여기서 남은 양수는 아무와도 짝을 짓지 않고 그냥 더해줄 것임
}
else if (positive != 0) { // 1보다 큰 양수가 짝수 개일 때
while (i < positive) { // 두 개씩 짝을 짓는 과정 (위와 똑같음)
sum += arr[N - i - 1] * arr[N - i - 2];
arr[N - i - 1] = 0;
arr[N - i - 2] = 0;
i += 2;
}
}
// 위의 과정이 끝났으면 더하지 않았던 수들(0, 1 또는 0, 1, 남은 양수)을 더해줌
for (i = 0; i < N; i++) {
sum += arr[i]; // sum에 포함한 arr[i]는 0으로 만들어서 다 더해도 영향을 주지 않음
}
printf("%d", sum);
free(arr);
return 0;
}
여기 /* 음수 부분 */ 중에서 if (negative % 2 == 1)안의 if문을 보자
if (negative % 2 == 1) { // 음수가 홀수 개일 때
while (i < negative - 1) { // 두 개씩 쌍을 짓고 남은 하나를 만들기 위해 'negative - 1'
sum += arr[i] * arr[i + 1];
arr[i] = 0; // sum에 더한 후 arr[i]과 arr[i+1]을 0으로 바꿔줌
arr[i + 1] = 0;
i += 2; // 두 칸 뒤로
}
// 위의 과정을 거치고 남은 음수 다음의 원소가 0이면, 0과 짝을 지어 곱해 더해야 sum이 최대가 됨
if (arr[i + 1] == 0 && N - 1 == i); // input: -3 -2 -1처럼 input에 음수만 있는 경우
else if (arr[i + 1] == 0) // 남은 음수 다음의 원소가 0일 때
arr[i] = 0; // 0과 곱한다 치고 값을 0으로 바꿔줌
}
아래 처럼 되어있는데,
if (arr[i + 1] == 0 && N - 1 == i); // input: -3 -2 -1처럼 input에 음수만 있는 경우
else if (arr[i + 1] == 0) // 남은 음수 다음의 원소가 0일 때
arr[i] = 0; // 0과 곱한다 치고 값을 0으로 바꿔줌
원래는 이 부분을 아래와 같이 했었다
if (arr[i + 1] == 0) // 남은 음수 다음의 원소가 0일 때
arr[i] = 0; // 0과 곱한다 치고 값을 0으로 바꿔줌
바로 이 부분이 틀린 부분이었다
위 코드처럼 하면 arr[i + 1]부분에서 malloc으로 만든 배열의 범위를 넘어갈 수 있어
undefined behavior가 된다는 것이었다
input이 -3 -2 -1처럼 홀수 개의 음수로만 이루어져 있을 때 문제가 된다
내가 사용하던 visual studio는 윈도우 환경이고
백준 채점 서버는 리눅스 환경으로 서로 다르다
N = 3, 수열: -3 -2 -1일 때
윈도우 환경에서는 arr = 2인 상황에서 if문 내의 arr[i + 1]는
arr[3]이 되어 자동으로 FALSE가 되는데
리눅스 환경에서는 배열의 범위를 초과하는 arr[i+1]는 0이 되어
해당 코드를 실행하게 되어 답이 6으로 나오게 된다
그래서 위의 코드를 저렇게 바꾸어 주었다
후... 답변해주신 알고리즘 톡방 분 감사합니다...ㅠㅠ
그 분께서 리눅스 환경인 웹 IDE 사이트도 알려주셨다...
Ideone.com
Ideone is something more than a pastebin; it's an online compiler and debugging tool which allows to compile and run code online in more than 40 programming languages.
ideone.com
2036번은 배열과 sum의 int형을 long long int형으로 바꿔주면 된다