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

(追記) (追記ここまで)

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

11378번 - 열혈강호 4

pjh9996 6년 전 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 6년 전 0

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

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

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

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC