[책-알고리즘퍼즐68]3.카드뒤집기

문제

1~100까지 카드가 뒤집어져 있다. n번쨰 카드를 n-1씩 이동하여 카드를 뒤집는다. (n초기값 = 2) 100번째 카드까지 이러한 과정을 거쳤을때 뒤집어져 있는 카드는 ?

예)  (■:뒤 □:앞)

n=2  ■□■□■□■□■□ 

n=3  ■□□□■■■□□□ 

n=4  ■□□■■■■■□□ 

 

난이도

IQ 70

 

목표시간

10분

 

문제풀이(사용언어:C#, 작성도구:VisualStudio2019)

//20.01.08
//
//

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _3_TurnCardOver
{
    class Program
    {
        static void Main(string[] args)
        {
            //0:뒤 1:앞
            int[] deck = new int[100];

            //deck 초기화(모든 카드가 뒤집힌 상태)
            for(int i=0; i<deck.Length; i++)
            {
                deck[i] = 0;
            }

            //뒤집기
            for (int i=2; i<=deck.Length; i++)
            {
                for(int j=i-1; j< deck.Length; j+=i)
                {
                    if (deck[j] == 0)
                        deck[j] = 1;
                    else
                        deck[j] = 0;
                }
            }

            //결과
            for (int i = 0; i < deck.Length; i++)
            {
                if (deck[i] == 0)
                {
                    Console.WriteLine(i+1);
                }

            }


        }
    }
}

 

문제정답(사용언어:python)

1. solution_1은 문제 그대로의 규칙대로 작성된 방법

2. solution_2는 제곱수(1,4,9,16 ..)만을 구하는 방법

 2.1 나열된 카드는 홀수 뒤집혔을때 앞면을 짝수번 뒤집혔을때 된다.

 2.2 예를 들어 16번 카드는 2 4 8 16번째 카드를 이동할떄 마다 뒤집힌다.

 2.3 2 4 8 16은 16의 약수이다

 2.4 즉 1~100까지 숫자 중에 약수가 홀수개인 숫자를 찾으면된다

 2.5 약수가 홀수개인 수는 제곱수이다.

 2.6 왜? 약수를 오름차순으로 나열했을때 각 끝 숫자들의 곱은 해당 숫자값이된다

 2.7 16의 약수의 경우 1*16=16, 2*8=16, 4*4 =16 가운데 남는 4는 4*4=16이 된다.

 2,.8 따라서 제곱수는 약수가 홀수개이다 제곱수는 문제의 정답수이다.  

# 카드의 초기화
N = 200
cards = [False] * N


## solutin_1
# 2~N까지 뒤집음
for i in range(2, N+1) :
    j=i-1
    while j < len(cards):
        cards[j] = not cards[j]
        j+=i

#뒷면이 위를 향한 카드 출력
for i in range(0,N):
    if not cards[i]:
        print(i+1)


##solutin_2
for i in range(1, N+1):
    flag = False
    for j in range(1, N+1):
        if i%j==0:
            flag = not flag
    if flag:
        print(i)

 

배운점

 파이썬의 쉬운 배열 초기화를 보고 c#에서도 가능한지 찾아보았다

    int[] myIntArray = Enumerable.Repeat(-1, 20).ToArray();

 단순히 규칙을 코드로 옮겨 문제를 풀었다. 코드로 옮기는대 시간이 걸리더라도 그전에 단순히 문제 그대로의 풀이 방식이 아닌 새로운 방법에 대해서 다양한 접근을 습관적으로하는게 좋을것 같다. 어려운 규칙은 단순화 시켜 코드작성을 하지만 단순한 규칙은 쉽게 생각을 멈추고 코딩하는 것 같다.