2-P번 질문

Question

코드 main 함수 부분 중에 int ans = 0;//조합 3개=3중 for문 for (int i = 0; i < v.size(); i++) { for (int j = 0; j < i; j++) { for (int k = 0; k < j; k++) { a[v[i].first][v[i].second] = a[v[j].first][v[j].second] = a[v[k].first][v[k].second] = 1;//벽 생성// ans = max(ans, solve()); a[v[i].first][v[i].second] = a[v[j].first][v[j].second] = a[v[k].first][v[k].second] = 0;//벽 해제-->초기화// } } } cout << ans; for문에서 i의 범위 설정은 알겠는데, j와 k의 범위 설정이 약간 이해가 가지 않아서 질문드립니다~~

큰돌 · Answer

안녕하세요. jtiger0303님ㅎㅎ 이부분은 조합이고 순서와 상관없이 뽑는 경우의 수를 말하죠. 예를 들어 0, 1, 2, 3 이라는 인덱스가 있을 때 순서와 상관없이 3개를 뽑는다고 하면 어떻게 될까요? 0, 1, 2 0, 1, 3 0, 2, 3 1, 2, 3 위와 같이 되겠죠? 다른 경우의 수는 없을겁니다. 벽을 생성하는 것도 이와 같습니다. 벽을 생성할 수 있는 좌표가 들어가있는 벡터를 기반으로 어떠한 "인덱스"에 해당하는 "벽"을 세우기만 하면 되는 것이니까요. 순서는 당연히 상관이 없죠.또한 3개의 벽을 세워야 합니다. 이 때 combi라는 재귀함수를 만들어서 할 수 있지만 3개이하정도는 3중 for문으로 할 수 있다고 설명을 드린바있습니다. #include < cstdio > #include < algorithm > #include < vector > #include < iostream > using namespace std; int n = 5 ; int k = 3 ; int a[ 5 ] = { 1 , 2 , 3 , 4 , 5 }; int main () { for ( int i = 0 ; i < n; i ++ ){ for ( int j = i + 1 ; j < n; j ++ ){ for ( int k = j + 1 ; k < n; k ++ ){ cout << i << " " << j << " " << k << ' ' ; } } } return 0 ; } /* 0 1 2 0 1 3 0 1 4 0 2 3 0 2 4 0 3 4 1 2 3 1 2 4 1 3 4 2 3 4 */ 예를 들어 5개의 요소를 가진 배열에서 3개를 뽑는다고 했을 때 이렇게 3중for문을 통해 코드를 실행시키면 확연히 모든 경우의 수가 뽑히는 것을 알 수 있습니다. * 참고로 for (int j = 0; j < i; j++) { 로 하는 것과 for (int j = i + 1; j < n; j++) { 이렇게 하는 경우 뽑히는 순서만 다르지 모든 경우의 수가 뽑히는 것은 동일합니다. 사실 이부분은 교안에 다 설명이 되어있습니다. 교안은 반드시 "외워 주셔야" 합니다. 또 질문사항있으시면 언제든 말씀 부탁드립니다. 감사합니다. 강사 큰돌 올림.