글 읽기 - [2614] 검은점과 하얀점 // 으으...이거 그리디 맞나요...?

QuqqU 4년 전 0

그리디하게 1와 0을 가까운 것끼리 최대한 연결하면 될 것 같아, 유니온 파인드를 이용했습니다

ex)

1100 이라면

첫번째와 두번째 1은 그냥 패스시키고,

세번째 0을 바로 앞수와 연결시켜서, pair (find(3-1), 3) == (2,3)을 답으로 저장하고, merge(find(3-1)-1, find(3-1))을 합니다.

네번째 0을 바로 앞수와 연결시켜서, pair (find(4-1), 4)==(1,4)을 답으로 저장합니다.

이렇게 했는데, 18%에서 틀립니다.

알고리즘이 틀린 걸까요? ㅠㅠㅠㅠ

도저히 감이 안오네요...

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> ii;

int n, r;
char a[105];
vector<ii> ans;

class Unionfind {
public:
	//parent는 자신의 조상 저장, rank[i]는 i번째에서의 세로길이 
    vector<int> parent, rank;
    
    
	Unionfind(int n) : parent(n), rank(n, 0) {
		for (int i = 0; i < n; i++) parent[i] = i;
	}

	int find(int me) {
		if (me == parent[me]) return me;
		return parent[me] = find(parent[me]);
	}
	void merge(int a, int b) {
		a = find(a); b = find(b);
		if (a == b) return;
		parent[a] = b;
	}
};

int main() {
	scanf("%d %s", &n, a);
	Unionfind uf(n + 1);
	int p = 0, rlt = 0;
    
    //1이 0보다 왼쪽에 있게 만들기
    //1010 01 이라면 1010은 패스
    //01은 10으로 만들기 (101001->101010)
	for (int i = 0; i < n; ) {
		a[i] == '1' ? p++ : p--;
		if (p < 0) {
			for (int j = i; j < n; j++)
				a[j] == '1' ? a[j] = '0' : a[j] = '1';
			p = 0;
		}
		else i++;
	}
    
    //1이 나오면 패스
    //0이 나오면 왼쪽에서 연결할 수 있는 1중에 가장 가까운 1을 찾아서 업데이트
	for (int i = 0; i < n; i++) {
		if (a[i] == '0') {
			int z = 0;
			uf.merge(i, i - 1);
			ans.push_back(ii(uf.find(i), i));//연결된 쌍 저장

            //연결된 쌍 사이에 존재하는 최대의 세로길이 구하기
			for (int j = uf.find(i); j <= i; j++)
				z = max(z, uf.rank[j]);
			
            // rlt에 가로길이 + 세로길이 * 2 누적 시키기
			rlt += i - uf.find(i) + 2 * (z + 1);
			
			uf.rank[uf.find(i)] = z + 1;
			uf.rank[i] = z + 1;

			if (uf.find(i) - 1 >= 0) uf.merge(uf.find(i), uf.find(i) - 1);
		}
	}



	sort(ans.begin(), ans.end());



	printf("%d\n", rlt);
	for (auto a : ans) printf("%d %d\n", a.first + 1, a.second + 1);
	return 0;
}

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

문제

문제

출처

ICPC

[2614] 검은점과 하얀점 // 으으...이거 그리디 맞나요...?

QuqqU 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말