[고전 알고리즘]: 불을 켜는 문제는 새로운 해법이 없는 것 같아...

1813 단어

제목.


n개의 등불이 있는데 번호가 1~n이다. 첫 번째 사람은 모든 불을 켜고, 두 번째 사람은 모든 번호가 2인 배수 스위치(이 등들은 꺼진다)를 누르고, 세 번째 사람은 모든 번호가 3인 배수 스위치를 누른다(그중 꺼진 등은 켜지고, 켜진 등은 꺼진다).
입력: 7 3 출력: 1 5 6 7

사고의 방향


사고방식도 매우 간단하다. 하나의 블라인드 그룹으로 램프의 스위치 상태를 저장하고true를 위해 켜져 있고false는 닫혀 있다. 그리고 한 번 훑어보면 된다. 자세한 내용은 코드를 보면 된다.

코드

#include<iostream>
using namespace std;
bool trek[100];
void main()
{
    int n,k;
    cin>>n>>k;
    memset(trek,true,100*sizeof(bool));//              true
    for(int i=2;i<=k;i++){
        int pos=i;
        while(pos<=n){
            trek[pos] = !trek[pos];  //  
            pos+=i;     //       
        }
    }
    for(i=1;i<=n;i++){      //  
        if(trek[i])  cout<<i<<" ";
    }
}

실행 캡처

좋은 웹페이지 즐겨찾기