초보자 알고리즘 질문 하나만요,ㅜ

  • 페브리즈
    페브리즈

    막 배우려고 하는 알고리즘 초보단계인데요..
    머 문제를 풀다 막히는게 있어서요.. 머 많은 문제를 푸신 분은 아시겟지만
    이거 문제요.
     원탁의 기사 모두가 용과 싸우고싶어 하지만 많은 군대를 이끌고 가면 용이 미리알아 채기 때문에 기사한명만이 갈 수 있다. 아더왕은 과연 누구를 보내야 하는가 고민에 빠졌다. 그러던 중 랜슬럿이 묘책을 제시하였다. 원탁에 둘러 앉아 있는 기사 n명에게 시계방향으로 차례대로 1번부터 n번의 번호를 부여 한다. 다음 그 중의 임의의 숫자 m을 선택하여 그 번호의 기사를 제외시킨다. 다음 그 기사로부터 시계방향으로 k번째 있는 기사를 제외시키는 작업을 단 한명이 남을때까지 계속한뒤, 그 결과 마지막으로 남는 기사가 용과 싸우러 가는 것이다. 예를 들어 n=8, m=2, k=3인 경우, 2번째 기사가 먼저 제외된후 이어 5번, 8번 기사가 차례대로제외된다. 원탁의 기사의 수 n, 처음 선택한 기사의 번호 m, 다음으로 몇 번째 기사를 제외시킬 것인가 하는 k가 주어질때, 제외되는 기사들의 번호를 순서대로 출력하고, 용과 싸우러 가게 되는 기사의 번호를 출력하는 프로그램을 작성하시오.
    <입력 형식>
    823
    <출력 형식>
    25841736
    이런식이요.
    제가 대충 malloc을 써서 풀긴했는데, 점점 고칠수록 틀려가서요,
     고수님들의 틀린부분 지적을 좀 해주세요.ㅜ

    #include <Stdio.h>
#include <stdlib.h>
int main()
{
      int i,j;
      int n, m, k;
      int *knight;
      scanf("%d %d %d", &n, &m, &k);
      knight = (int*)malloc(sizeof(int) * n);
 
      for(i = 0; i < n; ++i)
        knight[i] = 1;
 
       i = 0;
 
 while(i < n)
 {
      m = 0;
  
      j = (m + (k * i++)) % n;
      if(knight[j] == 1)
      knight[j] = 0;
      else
        knight[++j] = 0;
  
  for(k = 0; k <n; ++k)
  {
       if(knight[k] == 1)
       m = 100;
  }
  
      if(m == 0 || i == n-1)
     {
      printf("%d 번째 기사가 용을 잡으러 갑니다.\n", j);
        //break;
      }
 }
 return 0;
}
    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    15년 전
5개의 댓글이 있습니다.
  • Toivoa
    Toivoa

    답과는 상관이 없지만 일단 malloc을 했으면 메모리가 새지 않게 하기 위해서 free를 해주셔야 합니다.
    일단 틀린점을 하나만 지적하면 1번과 2번 기사가 빠졌을 때 j = (m + (k * i++)) % n; 에서 j = 1이 된다면 if문에서 2번 기사를 다시 제외하게 됩니다. 이런식으로 이미 빠져있는 기사들을 조금 더 고려해보세요.
    덧 - queue를 이용해서 풀면 쉽게 풀 수 있습니다.


    15년 전 link
  • 페브리즈
    페브리즈

    ..;;


    15년 전 link
  • Toivoa
    Toivoa 
    #include <cstdio>
#include <cstdlib>
using namespace std;
int main()
{
        int n, m, k;
        int *knight;
        scanf("%d%d%d", &n, &m, &k);
        knight = (int*)malloc(sizeof(int) * n);
        for (int i = 0; i < n; ++i)
                knight[i] = 1;
        printf("%d\n", m);
        knight[m - 1] = 0;
        int x = m - 1, z = n - 1;
        while (z > 1)
        {
                int y = k;
                do
                {
                        x++; x %= n;
                        if (knight[x] == 0) continue;
                        y--;
                } while (y);
                printf("%d\n", x + 1);
                knight[x] = 0;
                z--;
        }
        for (int i = 0; i < n; ++i)
                if (knight[i])
                {
                        printf("%d 번 기사가 용을 잡으러 갑니다.\n", i + 1);
                        break;
                }
        free(knight);
}

    15년 전 link
  • Toivoa
    Toivoa

    14 ~ 27 줄의 코드를 분석해보세요.


    15년 전 link
  • 페브리즈
    페브리즈

    네,ㅋㅋ 답변 감사합니다. 잘 분석해보겟습니다,.


    15년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.