내용

경쟁 프로, 초보자를 위한 내용
프로그램에서 겹치지 않는 조합을 생성하려면 어떻게 해야 합니까?

배경

AtCoder Beginner Contest 175의 B문제를 제출할 수 없었던 약약한 나.

B 문제
이 문제의 해설이라기보다는, 그 전 단계의 해설이 됩니다.

예제.

질문 1. 숫자가 적힌 5종류의 카드 중 3개를 선택한 조합은 몇 개입니까?

고등학생이라면 확실히 풀 수있는 문제
대답은 $_5C_3$ = 10

그러나, 경프로에서 요구되는 것은 조합의 총수보다, 각 조합이 조건에 맞는지에 대해서라고 하는 것.

질문 2. 각 조합의 카드의 합이 10 이하가 되는 것은, 어떻게 됩니까?
우선, 전체 조합을 얻을 필요가 있지만, 상기 공식만으로는 조합의 수는 알지만, 어떤 조합이 실제로 존재하고 있는지는 모른다. 일단 중학생으로 돌아가 수형도를 써보기로 한다.



이것을 하나하나 확인해 나가면 된다.

질문 3. 그것을 프로그램으로 나타냅니다.
경쟁 프로이므로 당연히 이렇게된다.

a. 그런 여유라면 프로그램으로 변환할 수 있는 사람
b. 전혀 모르는 사람
c. 여유라고 생각하고 쓰기 시작하고, 멈추는 사람(나)

a.의 사람은 더 이상 읽을 필요가 없습니다.

왜 프로그램으로 변환할 수 없는가?

수형도를 종이에 쓸 때에는 규칙성이 있기 때문에 익숙해지면 체계적으로 쓸 수 있다.

그러나 말로 설명하려고 하면. 처음에 A를 선택한 경우, A 이외의 B, C, D, E를 조합할 수 있다. 그 다음 B에 대해서는 A와 B 이외를 조합할 수 있다. ···· 첫째에 D를 선택한 경우에 조합되는 것은 E이지만, 그 다음의 3번째에 조합되는 것이 없기 때문에, 마지막 조합은 C-D-E가 된다.

상당히 복잡하고 프로그램으로 어떻게 표현하는지, 라고 어리석은 나만이 아니라고 생각한다.

해법

해법 1

전수 루프내를 작성해, 중복하지 않기 위한 조건을 추가( if(i>j && j>k)의 부분)

for(int i = 0; i < 5 ; i++){
  for(int j = 0; j < 5 ; j++){
　　for(int k = 0; k < 5 ; k++){
　    if(i>j && j>k){
　　　　 //重複のない組み合わせが出来上がる
        //和が10以上か確認する
      }
    }
  }
}

해법 2

루프의 조건으로 대응한다. (내부 루프의 j

for(int i = 0; i < 5 ; i++){
  for(int j = 0; j < i ; j++){
　　for(int k = 0; k < j ; k++){
      //重複のない組み合わせが出来上がる
      //和が10以上か確認する
    }
  }
}

과연, 만들어 보면 매우 간단. 그렇지만, 경프로의 긴장한 가운데 제로로부터 이것을 생각해낼 수 있을까. 나에게는 무리.

해법 이상으로 중요한 것.

하나의 패턴을 착용한 것.

조합으로부터, 조건에 맞는 것을 찾는 문제라고 깨달으면, 상기의 해법을 기억해, 간단한 루프를 만들 수 있다. 이것으로, 수형도는 쓸 수 있지만 어떻게 표현하면, 라고 오로오로 하고 있던 나와는 안녕.

실제로 상기 해법을 보면 매우 간단. 사람에 따라서는, 상기의 패턴을 사전에 모르더라도 갑자기 프로그램으로 변환할 수 있는 사람은 있을지도 모른다. 그렇지만, 모두가 모두 그렇지 않다고 생각한다. 적게 나에게는 어렵다, 그래서 이런 간단한 곳에서 패턴을 익혀가는 것이 중요하다고 생각한다.

남은 문제

모든 조합을 루프로 만들어 풀어도 좋은지,
이쪽이 절실한 생각이 든다.

100의 3중 루프 정도라면 괜찮다고 해설하고 있었다.
1000000회라고 생각하면, 그 정도 괜찮은 생각도 해왔다. 익숙한 필요?

수형도적인 순서에 맞는 방법

    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {