글 읽기 - 열혈강호4 while문을 for문으로 바꾸면 틀리는 이유을 알고싶습니다.

pjh9996 5년 전 1

64번 줄이 맞은 분들 코드를 참고한 AC받은 코드입니다.

74번 줄 코드가 기존에 제가 작성했던 코드인데 93%에서 WA를 받았습니다.

for문 조건식에서 j는 증가하고 k는 감소하면서 문제가 생길지 혹시나해서

85번 줄 코드처럼 별도의 변수를 둬서 처리했더니 정상적으로 AC를 받았습니다. 실행시간도 동일하구요.

"for문 조건식에서 j는 증가하고 k는 감소하면서 문제가 생길지" 에서 문제가 발생하는게 맞는지, 그 원인이 무엇인지 이해하고싶습니다.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <string>

using namespace std;
using pii = pair<int, int>;
using ll = long long;

int n, m, k;
vector<vector<int>> adj;
vector<bool> visited;
vector<int> parent;

int answer = 0;

void input()
{
	cin >> n >> m >> k;
	adj.resize(n);
	visited.resize(n);
	parent.resize(m, -1);
	for (int i = 0; i < n; i++) {
		int work;
		cin >> work;
		for (int j = 0; j < work; j++) {
			int wn;
			cin >> wn;
			adj[i].push_back(wn - 1);
		}
	}
}

void output()
{
	cout << answer;
}

bool bmatch(int now)
{
	visited[now] = true;
	for (int next : adj[now]) {
		if (parent[next] == -1 || (!visited[parent[next]] && bmatch(parent[next]))) {
			parent[next] = now;
			return true;
		}
	}
	return false;
}

void process()
{
	for (int i = 0; i < n; i++) {
		fill(visited.begin(), visited.end(), false);
		if (bmatch(i)) answer += 1;
	}
	for (int i = 0; i < n && answer < m; i++) {
        // 80ms AC 코드
		while(k) {
			fill(visited.begin(), visited.end(), false);
			if (bmatch(i)) {
				answer += 1;
				k -= 1;
			}
			else break;
		}
        
        /* WA 코드
        for(int j = 0; j < k; j++) {
            fill(visited.begin(), visited.end(), false);
            if(!bmatch(i) || answer == m) break;
            k -= 1; // 반복문 조건식에 사용되는 k를 감소시켰을 때 어떤 문제가 발생될 수 있나요?
            answer += 1;
        }
        if(answer == m) break;
        */
	}
    
    /* add변수를 추가해서 k에 변화를 주지않도록 구현하면 AC를 받습니다.
    int add = 0;
	for (int i = 0; i < n; i++) {
        for(int j = 0; j < k; j++) {
            fill(visited.begin(), visited.end(), false);
            if(!bmatch(i) || answer + add == m || add == k) break;
            add += 1;
        }
        if(answer + add == m || add == k) break;
	}
    answer += add;
    */
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	input();
	process();
	output();
	return 0;
}

dyk777 5년 전 0

75번 줄에 대해서만 간략하게 설명하면,

j++, k--가 동시에 이루어지면 결국 j와 k 사이의 간격이 2씩 줄어듭니다.

다른 코드들은 그 간격이 1씩 줄어드므로, 결국 반복문을 도는 횟수 자체가 2배정도 차이가 나게 됩니다.

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

문제

문제

출처

ICPC

열혈강호4 while문을 for문으로 바꾸면 틀리는 이유을 알고싶습니다.

pjh9996 5년 전 1

dyk777 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말