[백준 / BOJ] 1195 킥다운

문제

출처 : https://www.acmicpc.net/problem/1195

1195번: 킥다운

두개의 기어파트가 주어진다. 각 기어파트는 1과 2로 이루어져있는데, 1은 '홈(들어가있는 부분)' 2는 '이(나와있는 부분)'를 나타낸다

 

이 때, 두개의 기어파트를 적절히 조합하여 조합된 기어파트의 길이의 최솟값을 구하는 문제다.

---

풀이

기어의 길이가 최대 100이므로 완전탐색으로 풀리는 문제다.

 

문제에서 주어진 그대로 구현하면 되는데, 몇가지 주의할 점 이 있다.

- 기어가 맞물린다는것이 꼭 '1'과 '2'가 만나야 만 하는것은 아니다. '2'와 '2'가 만나는것이 아니라면 언제든 맞물릴수있다.

- 짧은파트를 움직일때 항상 최소 가로 길이가 나오는것이 아니다. 긴 파트를 움직일때 최소 가로 길이가 나올수도 있다. (짧은 파트를 왼쪽으로 움직였을때 최솟값이 나올수 있다는 말과 같은 의미이다.)

 

예시로, 문제의 예제는

2112112112
2212112

이 주어지고, 짧은 파트를 움직였을때, 최솟값 10이 나온다.

 

반면

121
122222

의 경우, 긴 파트를 오른쪽으로 움직였을때, 최솟값 7이 나온다.

 

주요 소스코드

	private int getCombinationSize(){
		int res = this.firstPart.length() + this.secondPart.length();
		for(int i = 0; i < secondPart.length(); i++){
			if(!this.isStringCombineable(i, this.firstPart, this.secondPart)) continue;
			res = min(res, max(this.firstPart.length() + i, this.secondPart.length()));
		}
		
		for(int i = 0; i < firstPart.length(); i++){
			if(!this.isStringCombineable(i, this.secondPart, this.firstPart)) continue;
			res = min(res, max(this.secondPart.length() + i, this.firstPart.length()));
		}
		return res;
	}
	
	private boolean isStringCombineable(int rightMoveIdx, String movePart, String staticPart){
		for(int i = 0; i < min(movePart.length(), staticPart.length()-rightMoveIdx); i++)
			if(!this.isCharCombineable(movePart.charAt(i), staticPart.charAt(i+rightMoveIdx))) return false;
		return true;
	}
	
	private boolean isCharCombineable(char moveC, char staticC){
		return !(moveC == '2' && staticC == '2') ? true : false;
	}

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/1195%20%ED%82%A5%EB%8B%A4%EC%9A%B4/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃