๋ฌธ์
2138๋ฒ: ์ ๊ตฌ์ ์ค์์น
N๊ฐ์ ์ค์์น์ N๊ฐ์ ์ ๊ตฌ๊ฐ ์๋ค. ๊ฐ๊ฐ์ ์ ๊ตฌ๋ ์ผ์ ธ ์๋ ์ํ์ ๊บผ์ ธ ์๋ ์ํ ์ค ํ๋์ ์ํ๋ฅผ ๊ฐ์ง๋ค. i(1 < i < N)๋ฒ ์ค์์น๋ฅผ ๋๋ฅด๋ฉด i-1, i, i+1์ ์ธ ๊ฐ์ ์ ๊ตฌ์ ์ํ๊ฐ ๋ฐ๋๋ค. ์ฆ, ๊บผ์ ธ
www.acmicpc.net
์ฝ๋
#include <iostream>
#define INF 1e6
using namespace std;
int switch_first = 0, switch_second = 1 ;
bool check(string blub, string make, int seq){
for(int i=1; i<blub.length(); i++){
if(blub == make) return true;
if(blub[i-1] != make[i-1]){
blub[i-1]=='0'?blub[i-1]='1':blub[i-1]='0';
blub[i]=='0'?blub[i]='1':blub[i]='0';
blub[i+1]=='0'?blub[i+1]='1':blub[i+1]='0';
if(seq==1) switch_first++;
else switch_second++;
}
}
if(blub == make) return true;
return false;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int N; cin>>N;
string blub, make; cin>>blub>>make;
//0๋ฒ ์๋๋ ธ์ ๋
bool flag1 = check(blub, make, 1);
if(!flag1) switch_first = INF;
//0๋ฒ ๋๋ ธ์ ๋
blub[0]=='1'?blub[0]='0':blub[0]='1';
blub[1]=='1'?blub[1]='0':blub[1]='1';
bool flag2 = check(blub, make, 2);
if(!flag2) switch_second = INF;
if(switch_first == INF && switch_second == INF) cout<<-1;
else cout<<min(switch_first, switch_second);
}
ํ์ด
๊ทธ๋ฆฌ๋ ๋ฌธ์ ์ง์ ํตํด ์์๋ถํฐ ๊ทธ๋ฆฌ๋๋ผ๋ ์ฌ์ค์ ์ธ์งํ๊ณ ์์์ง๋ง, ๊ทธ๋ ์ง ์์๋ค๋ฉด DP๋ก ์ ๊ทผํ๋ค๊ฐ ๊ฒฐ๊ตญ ๋ชป ํ์์ ๊ฒ ๊ฐ์๋ ๋ฌธ์ ์์ต๋๋ค. ๋์ ํ ํ์ด ์์ด๋์ด๋ฅผ ๋ ์ฌ๋ฆฌ์ง ๋ชปํด ์๋ ๋ ๋ธ๋ก๊ทธ์ ๊ธ์ ๋ณด๊ณ ํด๊ฒฐํ์ต๋๋ค.
๋ฌธ์ ํ์ด ์์ด๋์ด๋ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
์ข์ธก์ ์ ๊ตฌ๋ ์ ๊ฒฝ ์ฐ์ง ์๊ณ , ํ์ฌ ์ ๊ตฌ๊ฐ ๋ง๋ค์ด์ผ ํ๋ ์ ๊ตฌ์ ๊ฐ์์ง๋ฅผ ๋น๊ตํฉ๋๋ค.
- ํ์ฌ ์ธ๋ฑ์ค์ ์ ๊ตฌ๊ฐ ๋ง๋ค์ด์ผ ํ๋ ์ธ๋ฑ์ค์ ์ ๊ตฌ์ ๊ฐ๋ค๋ฉด ๋์ด๊ฐ๋๋ค.
- ๋ง์ฝ ํ์ฌ ์ธ๋ฑ์ค์ ์ ๊ตฌ๊ฐ ๋ง๋ค์ด์ผ ํ๋ ์ธ๋ฑ์ค์ ์ ๊ตฌ์ ๋ค๋ฅด๋ค๋ฉด ์ฐ์ธก์ ์ ๊ตฌ๋ฅผ ๋ณ๊ฒฝํฉ๋๋ค.
- ์ฆ, ์ข์ธก์ ์ ๊ตฌ๋ ์ ๊ฒฝ์ฐ์ง ๋ง๊ณ ํ์ฌ ์ ๊ตฌ๋ง ์ ๊ฒฝ ์จ์ ๋ง๋ ๋ค์ ์ต์ข ์ ์ผ๋ก ์ํ๋ ์ ๊ตฌ๊ฐ ๋๋ค๋ฉด ์ต์๊ฐ์ ๊ธฐ๋กํฉ๋๋ค.
๋ฐ๋ผ์ 0๋ฒ ์ธ๋ฑ์ค์ ์ ๊ตฌ๋ฅผ ๋๋ ์๋ ์ ๋๋ฅด์ง ์์์ ๋์ ์ค์์น์ ์ต์๊ฐ์ ์ถ๋ ฅํ๋ฉด ๋ฉ๋๋ค.
'Algorithm ๐ง๐ปโ๐ป > ๋ฐฑ์ค(BOJ)' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค,c++] 19637๋ฒ - IF๋ฌธ ์ข ๋์ ์จ์ค (0) | 2022.08.02 |
---|---|
[๋ฐฑ์ค,c++] 2812๋ฒ - ํฌ๊ฒ ๋ง๋ค๊ธฐ (0) | 2022.07.29 |
[๋ฐฑ์ค,c++] 13164๋ฒ - ํ๋ณต ์ ์น์ (0) | 2022.07.27 |
[๋ฐฑ์ค,c++] 1167๋ฒ - ํธ๋ฆฌ์ ์ง๋ฆ (0) | 2022.07.26 |
[๋ฐฑ์ค,c++] 9489๋ฒ - ์ฌ์ด (0) | 2022.07.26 |
[๋ฐฑ์ค,c++] 20924๋ฒ - ํธ๋ฆฌ์ ๊ธฐ๋ฅ๊ณผ ๊ฐ์ง (0) | 2022.07.24 |
๋๊ธ