C 프로그래밍으로 연속된 0 두 개와 1 세 개가 나오지 않도록 n개의 0과 m개의 1 출력하기

N개의 0과 M개의 1로 구성된 수열을 생성해야 하며, 만들어진 수열에는 연속된 두 개의 0과 연속된 세 개의 1이 포함되어서는 안 됩니다.

입력 − N=5, M=9

출력 − 1 1 0 1 1 0 1 1 0 1 0 1 0 1

참고 − 위와 같은 수열을 만들 수 있으려면 조건식 (m < n-1) || m >= 2 * (n + 1)이 반드시 거짓이어야 합니다. 만약 이 조건이 참이라면 주어진 개수로는 유효한 수열을 만들 수 없습니다.

아래의 정답 코드로 바로 넘어가기보다는, 먼저 문제의 풀이 로직을 이해한 뒤 스스로 해결해 보는 것을 권장합니다.

알고리즘

START
Step 1 -> 'n'과 'm'에 값을 입력받습니다
Step 2 -> IF m == n-1인 경우
    WHILE m > 0 AND n > 0 동안
        "01"을 출력
        m과 n을 각각 1씩 감소
    END WHILE
    IF n != 0
        남은 "0"을 출력
    END IF
    IF m != 0
        남은 "1"을 출력
    END IF
Step 3 -> ELSE IF (m < n-1) || m >= 2 * (n + 1)
    수열을 만들 수 없음을 출력
Step 4 -> ELSE
    WHILE m-n > 1 AND n > 0 동안
        "110"을 출력
        m은 2씩, n은 1씩 감소
    END WHILE
    WHILE n > 0 동안
        "10"을 출력
        m과 n을 각각 1씩 감소
    END WHILE
    WHILE m > 0 동안
        "1"을 출력
        m을 1씩 감소
    END WHILE
Step 5 -> END ELSE
STOP

예제 코드

#include <stdio.h>
#include <math.h>
int main() {
   int n = 5, m = 9;
   if( m == n-1 ) { // m이 n보다 1 작으면 0과 1을 번갈아 배치
      while( m > 0 && n > 0 ) { // m과 n이 모두 소진될 때까지 반복
         printf("01");
         m--;
         n--;
      }
      if ( n!=0 ) // 남은 0 출력
         printf("0");
      if( m!=0 ) // 남은 1 출력
         printf("1");
   }
   else if ( (m < n-1) || m >= 2 * (n + 1) ) { // 조건이 참이면 수열 생성 불가
      printf("Can't have sequence for this\n");
   } else {
      while( m-n > 1 && n > 0 ) { // 1이 더 많은 만큼 "110" 패턴 배치
         printf("1 1 0 ");
         m -= 2;
         n--;
      }
      while ( n > 0 ) { // 남은 0마다 "10" 패턴 배치
         printf("1 0 ");
         n--;
         m--;
      }
      while ( m > 0 ) { // 마지막으로 남은 1 출력
         printf("1 ");
         m--;
      }
   }
   return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

1 1 0 1 1 0 1 1 0 1 0 1 0 1

이 알고리즘의 핵심은 1의 개수가 많을 때 먼저 "110" 패턴을 최대한 배치하여 세 개의 1이 연속되지 않도록 하고, 이후 남은 0에 대해 "10" 패턴을 배치한 뒤, 마지막에 남은 1들을 출력하는 방식입니다. 이를 통해 연속된 두 개의 0과 세 개의 1이 모두 방지되는 유효한 수열을 얻을 수 있습니다.