[코드포스 Practice15] C. Odd sum

음.. 풀다가 왜맞틀하다 끝난 문제

 

지우는 건 가능하되 순서 바꾸는 건 불가하다. 하지만 결국 순서 섞어서 선택해도 똑같은거 아닌가 싶었음.

그래서 정렬해서 투포인터로 앞에 것부터 뺐다.

 

하지만 틀렸길래.. 예시 하나하나 돌려 봤는데 -999 -998 이런 경우에서 틀렸다.

이거 답은 -999인데 내 코드로는 -1997이 나온다. 

생각해보니 값 하나하나 비교하지 않은 것 같아서 값 하나씩 비교하는 걸 추가했다. 

 

그래도 결국 12에서 계속 틀림..

이제 콘테스트로 끝났으니 12를 확인해봅시다..

 

10
4836 -2331 -3456 2312 -1574 3134 -670 -204 512 -5504

내 답은 6015가 나오는데 정답은 8563이 나온다. 

 

 

오

확인해보니 이런 문제가 있었다.

 

 

 

그 다음 생각한 걸로는 최대 합을 구한 후 작은 홀수를 빼면 되겠다 싶었다. 

근데 이럼 -999 -998 일 때 해결못함...ㅠㅠ

 

다시 힌트 받아서 양수 / 음수 나눠서 풀었다.

 

어차피 최대 합은 양수들의 합일테니 양수합을 구하고, 합이 짝수이면 작은 홀수값으로 처리해주면 된다. 

그럼 -999 -998 같은 것도 처리 가능하다!

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
 
using namespace std;
using i64 = long long;
 
i64 ft_abs(i64 num)
{
    if (num < 0)
        return -1 * num;
    return num;
}
 
int main() {
    i64 n;
    i64 sum = 0;
    scanf("%lld", &n);
    vector<i64> v(n);
    vector<bool> check(n, false);
    
    i64 min_odd_idx = -1;
    for (i64 i = 0; i < n; i++)
    {
        scanf("%lld", &v[i]);
        
        if (v[i] > 0)
        {
            sum += v[i];
            check[i] = true;
        }
        
        if (ft_abs(v[i]) % 2 == 1 && min_odd_idx == -1)
            min_odd_idx = i;
    }
    if (sum % 2 == 1)
    {
        printf("%lld", sum);
        return 0;
    }
    
    for (i64 i = 0; i < n; i++)
    {
        if (ft_abs(v[i]) % 2 == 1 && ft_abs(v[i]) < ft_abs(v[min_odd_idx]))
        {
            min_odd_idx = i;
        }
    }
    if (check[min_odd_idx])
        sum -= v[min_odd_idx];
    else
        sum += v[min_odd_idx];
                
    printf("%lld", sum);
    
    return 0;
}

 

코드는 이렇게 짰다. 

 

1. 양수 합을 구한다.

2. 양수합이 홀수이면 출력 후 종료, 짝수라면 홀수 값을 처리한다

3. 가장 작은 홀수 값을 구한다. 

     - 절댓값이 가장 작은 게 가장 작은 홀수

4. 만약 이 홀수가 합에 사용된 홀수라면 빼고, 합에 사용되지 않은 홀수라면 더한다.

 

끝~~

 

지금 생각났는데 합에 사용된건지 아닌지는 양수 / 음수로 확인할 수 있을 것 같다.

그럼 배열 사용 안 해도 될 듯?

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
 
using namespace std;
using i64 = long long;
 
i64 ft_abs(i64 num)
{
    if (num < 0)
        return -1 * num;
    return num;
}
 
int main() {
    i64 n;
    i64 sum = 0;
    scanf("%lld", &n);
    vector<i64> v(n);
    
    i64 min_odd_idx = -1;
    for (i64 i = 0; i < n; i++)
    {
        scanf("%lld", &v[i]);
        
        if (v[i] > 0)
            sum += v[i];
        if (ft_abs(v[i]) % 2 == 1 && min_odd_idx == -1)
            min_odd_idx = i;
    }
    if (sum % 2 == 1)
    {
        printf("%lld", sum);
        return 0;
    }
    
    for (i64 i = 0; i < n; i++)
    {
        if (ft_abs(v[i]) % 2 == 1 && ft_abs(v[i]) < ft_abs(v[min_odd_idx]))
        {
            min_odd_idx = i;
        }
    }
    if (v[min_odd_idx] > 0)
        sum -= v[min_odd_idx];
    else
        sum += v[min_odd_idx];
                
    printf("%lld", sum);
    
    return 0;
}

 

배열없애고 다시 제출했더니 맞았다!

 

워후 C도 클리어