[LINE] 2020 상반기 코딩테스트 3번 문항 C++

테스트케이스 통과한 코드만 올리겠뜹니다~

트리구조 생각해서 재귀를 사용해서 구현했다.

int solution(string road, int n) {
	int answer = -1;
	int temp = 0;
	int zero_cnt = 0;

	for (int i = 0; i < road.length(); i++) {
		if (road[i] == '0') {
			zero_cnt++;
		}
	}

	if (zero_cnt == 0 or n == 0) {
		int length = 0;
		int max = 0;
		for (int i = 0; i < road.length(); i++) {
			if (road[i] == '1') {
				length++;
			}
			else {
				if (max < length) {
					max = length;
					length = 0;
				}
			}
		}
		if (max < length) {
			max = length;
			length = 0;
		}
		return max;
	}

	for (int i = 0; i < road.length(); i++) {
		if (road[i] == '0') {
			road[i] == '1';
			temp = solution(road, n - 1);
			if (answer < temp) {
				answer = temp;
			}
			road[i] = '0';
		}
	}
	return answer;
}