[백준 11565] 바이너리 게임 [Java]

문제

http://boj.ma/11565

요약

• 문자열 a를 b로 만들 수 있는지 판별하자.
• 문자열 a의 맨 앞 문자를 제거할 수 있다.
• 문자열 a의 1의 개수가 홀수면 1을 추가하고, 짝수면 0을 추가할 수 있다.

---

풀이 과정

아이디어

문자열 a의 1의 개수가 홀수면 1을 추가한다.

이후 1의 개수는 짝수가 되므로 0만 추가할 수 있다.

즉 문자열 a의 1의 개수가 홀수일 때는 원래 개수 + 1, 짝수일 때는 원래 개수가 최대 한도이다.

if (cntA % 2 == 0) {
	return cntA >= cntB;
}
return cntA + 1 >= cntB;

성능 분석

• 시간 복잡도: $O(N)$
• 제출결과: Accepted / 100ms / 14324KB

---

참고

문제

http://boj.ma/11565

11565번: 바이너리 게임

 

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/gold/11565.java

problem-solving/baekjoon-online-judge/gold/11565.java at main · rogi-rogi/problem-solving