글 읽기 - memset 0 초기화 관련 질문드려요 ㅠㅠ

leedh2004 4년 전 0

다음 문제는 예상등수 최소화를 하는 건데..

제가 푼 방법은 처음에 예상등수로 선택되지 않은 등수를 스택에 쌓습니다. (top이 제일 작아야함)

그 다음에 배열을 한 번 예상등수를 sort 해주고,

1. 예상등수를 i라 할때 i 등수를 누군가 선점하지 않았다면 배정해주고 넘어갑니다.

2. i등수를 누군가에게 선점당했다면, stack에서 top() 에 있는 등수를 선점합니다.

이런식으로 푸는 과정에서 선점하는 배열을 chk 배열을 이용했습니다.

그런데 계속 틀렸습니다가 떠서 멘붕으로 하나씩 고치던 중에, memset(chk, 0, sizeof(chk)) 를 for문으로 하나씩 0을 넣으니까 맞았습니다가 뜨더군요..

제 생각에는 어차피 다 0 초기화 하는건데 왜 memset 을 썼을 때 틀렸습니다가 떴는지 이해가 안됩니다 ㅠㅠ

코드 주석처리 하겠습니다.

#include <iostream>
#include <algorithm>
#include <cmath>
#include <stack>
#include <cstring>

using namespace std;

int a[500001];
int chk[500001];
typedef long long ll;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> a[i];
        chk[a[i]] = 1; // 예상 등수를 선점함 
    }
    sort(a, a + n);
    
    ll ans = 0;
    stack<int> s;

    for(int i=n; i>=1; i--){ // 비어있는 등수들을 stack에 없는 수들을 내림차순으로 push
        if(!chk[i]) s.push(i);
    }
    
/////////////////////////////////질문//////////////////////////////////

    //memset(chk, 0, sizeof(chk)); // 이렇게하면 틀렸습니다..
    for(int i=1; i<=n; i++) chk[i] = 0; // 이렇게 하면 정답처리 됨..?

///////////////////////////////////////////////////////////////////////

    for(int i=0; i<n; i++){
        int here = a[i]; // 예상등수
        
        if(!chk[here]){ // 선점되지 않았다면 선점하고 넘어감
            chk[here] = 1;
        }else{ // 예상등수를 선점당했다면, 정렬된 배열이기 때문에 내림차순된 stack의 top()을 선점해야 최소값임.
            int j = s.top(); 
            s.pop();
            ans += abs(j - here);
            chk[j] = 1;
        }
    }
    cout << ans;
    return 0;
}

ekzmzm79 4년 전 1

//memset(chk, 0, sizeof(chk)); // 이렇게하면 틀렸습니다..

for(int i=1; i<=n; i++) chk[i] = 0; // 이렇게 하면 정답처리 됨..?

초기화 시키는 범위가 다르네요.

djm03178 4년 전 1

등수는 n과 관계 없이 50만 이하이기 때문에 둘의 동작은 서로 다릅니다. memset은 무조건 50만을 전부 초기화하고, for문은 1부터 n까지만 초기화합니다.

leedh2004 4년 전 0

아.. 5명 밖에 없는데 예상등수가 50만일수도 있는건가요? 이상한 학생이네요.. ㅠㅠ

leedh2004 4년 전 0

다음처럼 하니 memset도 맞네요. 감사합니다!

#include <iostream>
#include <algorithm>
#include <cmath>
#include <stack>
#include <cstring>

using namespace std;

int a[500001];
int chk[500001];
typedef long long ll;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> a[i];
        chk[a[i]] = 1; // 예상 등수를 선점함 
    }
    sort(a, a + n);
    
    ll ans = 0;
    stack<int> s;

    for(int i=n; i>=1; i--){ // 비어있는 등수들을 stack에 없는 수들을 내림차순으로 push
        if(!chk[i]) s.push(i);
    }
    
/////////////////////////////////질문//////////////////////////////////

    memset(chk, 0, sizeof(chk)); // 이렇게하면 틀렸습니다..
    //for(int i=1; i<=n; i++) chk[i] = 0; // 이렇게 하면 정답처리 됨..?

///////////////////////////////////////////////////////////////////////

    for(int i=0; i<n; i++){
        int here = a[i]; // 예상등수
        
        if(!chk[here] && here <= n){ // 선점되지 않았다면 선점하고 넘어감
            chk[here] = 1;
        }else{ // 예상등수를 선점당했다면, 정렬된 배열이기 때문에 내림차순된 stack의 top()을 선점해야 최소값임.
            int j = s.top(); 
            s.pop();
            ans += abs(j - here);
            chk[j] = 1;
        }
    }
    cout << ans;
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

memset 0 초기화 관련 질문드려요 ㅠㅠ

leedh2004 4년 전 0

ekzmzm79 4년 전 1

djm03178 4년 전 1

leedh2004 4년 전 0

leedh2004 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말