본문으로 바로가기

반복적인 계산을 함수를 사용하여 재귀적으로 풀면 해결할 수 있다.

4673: 셀프 넘버

#include <cstdio>

bool sn[10001];// 생성자 유무를 저장하는 배열

void f (int);// d(n)

int main() {
  for (int i=1; i<=10000; i++) {
    // 생성자가 없는 셀프 숫자이면 출력한다
    if (sn[i] == false) {
      printf("%d\n", i);
    }
    f(i);// 해당 숫자를 이용하여 무한 수열 생성
  }
  return 0;
}

void f (int n) {
  int n1 = n%10;
  int n2 = (n/10)%10;
  int n3 = (n/100)%10;
  int n4 = (n/1000)%10;
  int n5 = (n/10000)%10;
  int tmp = n + n1 + n2 + n3 + n4 + n5;
  
  // 다음의 조건을 통해 불필요한 함수의 반복을 회피한다
  if (tmp <= 10000 && !sn[tmp]) {
    sn[tmp] = true;// tmp의 생성자는 n이다
    f(tmp);
  }
}

생성자의 유무를 저장하는 배열을 전역적으로 선언하고 생성자가 있는 숫자를 지우는 함수를 재귀적으로 호출함으로써 셀프 넘버를 추려낸다. 이미 생성자가 있는 숫자는 이미 재귀 함수를 한 번 거쳤으므로 반복해서 함수를 호출하는 불필요함을 덜어주자.

1065: 한수

#include <cstdio>

bool f (int);// 한수인지 확인하는 함수

int main() {
  int n;
  scanf("%d", &n);
  
  int k = 0;
  for (int i=1; i<=n; i++) {
    f(i) ? k++ : k;
  }
  
  printf("%d\n", k);
  return 0;
}

bool f (int n) {
  if(n < 100) return true;
  if(n < 1000){
    int a = (n/100)%10;
    int b = (n/10)%10;
    int c = n%10;
    return a-b == b-c;
  }
  return false;
}

잘 생각해보면 99이하의 숫자는 무조건 한수이다. 1000은 한수가 아니니까 세 자리 숫자를 비교하여 등차수열이 되는지만 확인하면 된다.

2448: 별찍기 - 11

#include <cstdio>
#include <cmath>

const int Y = 3 * 1024;
const int X = 2 * Y - 1;
const int M = X / 2;

bool map[X][Y];// 별을 그릴 도화지

void f (int, int, int);// 별을 그리는 함수

int main() {
  int n;
  scanf("%d", &n);
  
  f(M, 0, n);
  
  for (int i=0; i<n; i++) {
    for (int j=M-n+1; j<=M+n-1 ; j++) {
      if (map[j][i]) {
        printf("*");
      } else {
        printf(" ");
      }
    }
    printf("\n");
  }
  
  return 0;
}

// 중심점(x, y) 높이(h)의 삼각형을 그리는 함수
void f (int x, int y, int h) {
  if (h == 3) {
    map[x][y] = true;
    map[x-1][y+1] = map[x+1][y+1] = true;
    map[x-2][y+2] = map[x-1][y+2] = map[x][y+2] = map[x+1][y+2] = map[x+2][y+2] = true;
  } else {
    f(x, y, h/2);// 위쪽 삼각형
    f(x-h/2, y+h/2, h/2);// 왼쪽 아래 삼각형
    f(x+h/2, y+h/2, h/2);// 오른쪽 아래 삼각형
  }
}

재귀 함수를 사용하되 도화지에 별을 그린다는 느낌으로 문제를 풀었다. 배열을 좌표 평면으로 생각하고 별을 그려야하는 좌표에 true를 할당하여 해당 배열의 값이 true면 별을 출력했다.


댓글을 달아 주세요