Hello Ocean! ๐ŸŒผ

[๋ฐฑ์ค€/C++] 1013. Contact ๋ณธ๋ฌธ

Algorithm

[๋ฐฑ์ค€/C++] 1013. Contact

bba_dda 2021. 10. 26. 21:19
๋ฐ˜์‘ํ˜•

๋ฌธ์ œ

https://www.acmicpc.net/problem/1013

 

1013๋ฒˆ: Contact

์ž…๋ ฅ์˜ ์ฒซ ์ค„์—๋Š” ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜ T๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ทธ ๋‹ค์Œ ์ค„๋ถ€ํ„ฐ ๊ฐ๊ฐ์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์— ๋Œ€ํ•ด ์ „ํŒŒ๋ฅผ ํ‘œํ˜„ํ•˜๋Š”, { 0, 1 }๋งŒ์œผ๋กœ ์ด๋ฃจ์–ด์ง„ ๋ฌธ์ž์—ด์ด ๊ณต๋ฐฑ ์—†์ด ์ฃผ์–ด์ง„๋‹ค. ๋ฌธ์ž์—ด ๊ธธ์ด๋Š” (1 ≤

www.acmicpc.net

๋ฌธ์ œ๊ฐ€ ๊ต‰์žฅํžˆ ๊ธธ๊ณ  ๋ณต์žกํ•˜๋‹ค.. ๊ผผ๊ผผํžˆ ์ฝ์–ด๋ณด๋ฉด์„œ ์ดํ•ดํ•˜๋Š” ์‹œ๊ฐ„์ด ํ•„์š”ํ•˜๋‹ค. 

์š”์•ฝํ•˜์ž๋ฉด, ๊ฒฐ๊ณผ์ ์œผ๋กœ ์ž…๋ ฅ๋ฐ›์€ ๋ฌธ์ž์—ด์ด (100+1+|01)+ ํŒจํ„ด์— ํ•ด๋‹นํ•˜๋Š”์ง€ ์•„๋‹Œ์ง€๋ฅผ ํŒ๋‹จํ•˜๋ฉด ๋˜๋Š” ๋ฌธ์ œ์ด๋‹ค.

ํ’€์ด

(100+1+|01)+๋ฅผ ์ชผ๊ฐœ์„œ ๋ณด์ž. 

100+1+ = A, 01 = B๋ผ๊ณ  ํ•˜๋ฉด,

(A|B)+ ์ด๋ฏ€๋กœ, A๋‚˜ B๊ฐ€ ๊ณ„์† ๋ฐ˜๋ณต์ ์œผ๋กœ ๋‚˜ํƒ€๋‚˜๋ฉด ๋œ๋‹ค. 

B๋Š” 01 ์ž์ฒด์ด๊ณ , 

A ๋Š” 100+1+์ด๋‹ค. A๋ฅผ ๋” ๋œฏ์–ด๋ณด๋ฉด, 

10 0(0...) 1(1...) ์ด๋Ÿฐ์‹์ด๊ธฐ ๋•Œ๋ฌธ์— 1001๋ถ€ํ„ฐ ...์ž๋ฆฌ์— 0์ด๋‚˜ 1์ด ๋ช‡๊ฐœ๋“  ๋” ๋“ค์–ด๊ฐ€๋„ ๋˜๋Š” ๊ตฌ์กฐ์ด๋‹ค. 

 

๋ณต์žกํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์ƒ๊ฐ์ด ์•ˆ๋‚˜์„œ, ๊ทธ๋ƒฅ ๋ฌธ์ž์—ด ๋งจ ์•ž์—์„œ๋ถ€ํ„ฐ ํŒจํ„ด์œผ๋กœ if/else๋กœ ๋‚˜๋ˆ ์„œ ์žฌ๊ท€๋ฅผ ๋Œ๋ฆฌ๋Š” ๋ฐฉ์‹์œผ๋กœ ๊ตฌํ˜„ํ–ˆ๋‹ค. 

๋จผ์ € ๋งจ ์•ž์ด 1์ด๋ผ๋ฉด

100+1+์ธ์ง€ ํ™•์ธํ•ด์•ผ ํ•œ๋‹ค. ์ฆ‰ 1๋‚˜์˜ค๊ณ  ์ ์–ด๋„ 0์ด 2๊ฐœ, ์ ์–ด๋„ 1์ด 1๊ฐœ ๋‚˜์˜ค๋Š”์ง€ ํ™•์ธํ•ด๋ณธ๋‹ค. 

๊ทธ๋ฆฌ๊ณ , 1์ด 1๊ฐœ ์ด์ƒ์ผ ๊ฒฝ์šฐ ๋งˆ์ง€๋ง‰ 1๋’ค์— ๋‚˜์˜ค๋Š” 0์˜ ๊ฐœ์ˆ˜๋ฅผ ์ถ”๊ฐ€๋กœ ํ™•์ธํ•ด์„œ 

0์ด 1๊ฐœ๋ฉด : ๋งˆ์ง€๋ง‰1๊นŒ์ง€ ๋ฒ„๋ฆฌ๊ณ  ๋‚จ์€ ๋ฌธ์ž์—ด๋กœ ๋ฐ˜๋ณตํ•œ๋‹ค. (๋‹ค์Œ ํŒจํ„ด์ด 01์ด๊ธฐ ๋•Œ๋ฌธ์—)

ex) 100101... -> 01... , 1000111101... -> 01... 

0์ด 2๊ฐœ ์ด์ƒ์ด๋ฉด : ๋งˆ์ง€๋ง‰ 1์„ ๋‚จ๊ธด ๋ฌธ์ž์—ด๋กœ ๋ฐ˜๋ณตํ•œ๋‹ค (๋‹ค์Œ ํŒจํ„ด๋„ 100+1+์ด๊ธฐ ๋•Œ๋ฌธ์—)

ex ) 10011000... -> 1000... , 1001111110001... -> 10001...

 

๋งจ ์•ž์ด 0์ด๋ผ๋ฉด,

01์„ ์ž๋ฅด๊ณ  ๋‚จ์€ ๋ฌธ์ž์—ด๋กœ ๋ฐ˜๋ณตํ•œ๋‹ค. 

 

์ด๋ ‡๊ฒŒ ์žฌ๊ท€๋ฅผ ๋Œ๋‹ค๊ฐ€, ์กฐ๊ฑด์— ๋งž์ง€ ์•Š๋Š” ๊ฒฝ์šฐ๊ฐ€ ๋‚˜์˜ค๋ฉด ํŒจํ„ด์„ ๋งŒ์กฑํ•˜์ง€ ์•Š๋Š”๊ฒƒ์œผ๋กœ ํŒ๋‹จํ•˜๋ฉด๋œ๋‹ค. 

์ฝ”๋“œ๋ฅผ ๋ณด๋Š”๊ฒŒ ๋” ์ดํ•ด๊ฐ€ ์‰ฌ์šธ ๊ฒƒ ๊ฐ™๋‹ค..!

์ฝ”๋“œ

#include <iostream>
#include <string>

#define endl '\n'

using namespace std;

bool recursive(string s) {
	bool flag = false;
	int size = s.size();
	if (size == 0) return true;
	if (s[0] == '0') 
		if (s[1] == '1') flag |= recursive(s.substr(2)); // 01์ž๋ฅด๊ณ  ๋ฐ˜๋ณต
	else { // s[0] == '1'
		// 0 ๊ตฌ๊ฐ„
		int i = 1;
		while (i < size && s[i] == '0') {
			i++;
		}
		if (i <= 2) {
			return flag;
		}
		// 1 ๊ตฌ๊ฐ„ 
		int j = i;
		while (j < size && s[j] == '1') {
			j++;
		}
		// 1์ด 1๊ฐœ
		if (j == i + 1)
			flag |= recursive(s.substr(j));
		// 1์ด 2๊ฐœ ์ด์ƒ์ผ ๋•Œ ๋งˆ์ง€๋ง‰ 1 ๋’ค์— 0 ๊ฐœ์ˆ˜ ํ™•์ธ
		if (j >= i + 2) {
			if (j == size - 1) return flag;
			if (j + 1 < size && s[j + 1] == '0') 
				flag |= recursive(s.substr(j-1));
			else 
				flag |= recursive(s.substr(j));
		}
	}
	return flag;
}
int main() {
	int N; cin >> N;
	for (int n = 0;n < N;n++) {
		string input; cin >> input;
		string answer = (recursive(input)) ? "YES" : "NO";
		cout << answer << endl;
	}
	return 0;
}

๊ฒฐ๊ณผ

๋ฐ˜์‘ํ˜•