17142.cpp

바이러스 조건에 대한 설명이 참 부족한 문제 같다. 굉장히 많은 사람들을 혼란하게 만든 듯..

 

나도 참 이해가 안됐었는데 이렇게 생각하니까 그나마 이해가 됐다.

 

1. 우리가 구하고자 하는 건 빈 공간에 바이러스가 퍼지는 시간이다.

즉  ( 2 == 활성, * == 비활성, 0 == 빈 공간)

2 0 0 *

이라면, 답은 2초이다.

 

2. 비활성 바이러스가 활성 바이러스가 되는 데 걸리는 시간은 1초가 맞다.

즉

2 0 * 0

이라면, 답은 3초이다.

 

3. 비활성 바이러스가 활성 바이러스가 되는데 걸리는 시간은 이런 경우에 고려할 필요가 없다.

즉

2 * * *

이라면, 답은 0초이다.

 

왜냐하면 승원이가 구하고자 하는 시간은 "빈" 공간에 바이러스(비활성, 활성 상관없음)를 전파시키는데 걸리는 시간이기 때문이다. 결국 우리는 시간을 언제 갱신할지만 잘 고려하면 된다.

 

우리가 시간을 떠올리면 절대적인 시간을 생각하다 보니 문제에서 요구하는 시간의 개념과 헷갈리는 부분이 발생하는 것 같다.

 

차이점을 잘 인지하면 문제를 구현하는데 큰 어려움이 없다.

---

그리고 이 문제에서 CPP를 사용하시는 많은 분들이 조합을 구할 때 재귀 함수를 사용하는 것을 보았다. 하지만 귀찮게 굳이 그럴 필요 없으므로 간단한 방식을 소개한다.

vector<int> subArr = {0, 0, 0, 0, 0, 1, 1, 1};

do {
	// use subArr for indexing
} while(next_permutation(subArr.begin(), subArr.end()));

위 코드처럼 보조 수열을 하나 만든다. 보조 수열을 만들 때에는 직접 0과 1을 집어넣으면 된다. M개를 고르는 조합을 구하고 싶다면 1을 M개만큼 집어넣고 나머지는 0으로 채우라는 뜻... 1이 뒤에 와야 한다.

 

예시의 보조 수열이 의미하는 것은 8가지의 선택지에서 3개의 선택을 하겠다는 것이다.

즉 1의 위치를 선택한 index라고 생각하고 조합을 만들고 싶은 배열의 index를 참조하면 된다. 초기 subArr의 경우 5,6,7번 요소가 선택된 것이다.

저렇게 보조 수열을 만들고 next_permutation을 계속 호출하면 중복 없는 모든 조합을 구할 수 있게 된다.

 

나름 쓸만하다 ^^

 

---

코드는 아래 링크에서

https://github.com/seaworld0125/boj-hard-training/blob/main/17142/17142.cpp

GitHub - seaworld0125/boj-hard-training: 매일 1문제 + 해설

https://github.com/seaworld0125/boj-hard-training/blob/main/17142/17142.md

GitHub - seaworld0125/boj-hard-training: 매일 1문제 + 해설