본문으로 바로가기

각 사이클마다 반복적으로 나타나는 규칙을 찾아 문제를 해결하는 단계이다.

2438: 별찍기 - 1

#include <cstdio>

int main() {
  int n;
  scanf("%d", &n);
  
  for (int i=1; i<=n; i++) {
    for (int j=1; j<=i; j++) {
      printf("*");
    }
    puts("");
  }
  
  return 0;
}

2292: 벌집

#include <cstdio>
#include <cmath>

int main() {
  int n;
  scanf("%d", &n);
  n--;// 1번 방은 논외로 한다
  
  int k = 1;
  while (n > 0) {
    n -= 6*k++;// 지나야 하는 방의 개수는 6의 배수만큼 늘어난다 
  }
  
  printf("%d\n", k);
  return 0;
}

1개의 방을 지나야하는 벌집의 개수는 1개, 2개의 방을 지나야하는 벌집의 개수는 6개, 3개의 방을 지나야하는 벌집의 개수는 12개, 계속 6의 배수씩 늘어나는 규칙이다.

1193: 분수찾기

#include <cstdio>

int main() {
  int x;
  scanf("%d", &x);
  
  int k = 0;
  while (x > 0) {
    x -= ++k;
  }
  
  x += k;
  if (k % 2 == 0) {
    printf("%d/%d\n", x, k-x+1);
  } else {
    printf("%d/%d\n", k-x+1, x);
  }
  
  return 0;
}

분수가 몇 번째 대각선 상에 있는지를 먼처 찾고 분자와 분모의 합이 일정하다는 규칙을 이용하면 된다. 주의할 점은 홀수 대각선 상과 짝수 대각선 상의 방향이 다르다는 것이다.

1011: Fly me to the Alpha Centauri

#include <cstdio>
#include <cmath>

int main() {
  int t;
  scanf("%d", &t);
  
  while (t--) {
    int x, y;
    scanf("%d %d", &x, &y);
    
    int n = y-x;
    int k = 0;
    while (n > pow(++k, 2));
    
    n = y-x;
    printf("%d\n", n <= pow(k, 2) - k ? 2*k-2 : 2*k-1);
  }
  
  return 0;
}

n번 이동으로 최대로 이동할 수 있는 거리는 n이 홀수이면 (n/2+1)^2이고 n이 짝수이면 (n/2+1)^2 - (n/2+1)이다.

10250: ACM 호텔

#include <cstdio>

int main() {
  int t;
  scanf("%d", &t);
  
  while (t--) {
    int h, w, n;
    scanf("%d %d %d", &h, &w, &n);
    printf("%d%02d\n", (n-1)%h + 1, (n-1)/h + 1);
  }
  
  return 0;
}

1924: 2007년

#include <cstdio>

const int month[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const char weekday[7][4] = {"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};

int main() {
  int x, y;
  scanf("%d %d", &x, &y);
  
  int day = y;
  for (int i=1; i<x; i++) {
    day += month[i-1];
  }
  
  //  printf("%d\n", day);
  printf("%s\n", weekday[day%7]);
  return 0;
}

2775: 부녀회장이 될테야

#include <cstdio>

int dp[15][15];// dp[k][n]: k층 n호에 사는 사람의 수
int f (int, int);

int main() {
  int t;
  scanf("%d", &t);
  
  while (t--) {
    int k, n;
    scanf("%d %d", &k, &n);
    printf("%d\n", f(k, n));
  }
  
  return 0;
}

int f (int k, int n) {
  if (k == 0) return n;
  if (n == 1) return 1;
  if (dp[k][n]) return dp[k][n];
  return dp[k][n] = f(k-1, n) + f(k, n-1);
}

k층 n호 주민의 수는 (k-1)층 n호 주민의 수와 k층 (n-1)호 주민의 수의 합이다.

1475: 방 번호

#include <cstdio>
#include <cstring>

int main(int argc, const char * argv[]) {
  char rn[8];// room number
  scanf("%7[^\n]s", rn);
  
  int a[10];// 필요한 숫자의 개수를 저장하는 배열
  memset(a, 0, sizeof(a));
  
  auto l = strlen(rn);
  for (auto i=0 ; i<l ; i++){
    a[rn[i] - '0']++;
  }
  
  a[6] = (a[6]+a[9])/2 + (a[6]+a[9])%2;
  
  int ans = 0;
  for (int i=0 ; i<9 ; i++) {
    ans = ans > a[i] ? ans : a[i];
  }
  
  printf("%d\n", ans);
  return 0;
}

6064: 카잉 달력

#include <cstdio>

int getGCD(int, int);// 최대공약수를 구하는 함수
int getLCM(int, int);// 최소공배수를 구하는 함수

int main() {
  int t;
  scanf("%d", &t);
  
  while (t--) {
    int m, n, x, y;
    scanf("%d %d %d %d", &m, &n, &x, &y);
    
    int nMaxDay = getLCM(m, n);// m, n의 최소공배수로 카잉 제국이 멸망하는 날
    
    while (x <= nMaxDay) {
      if((x-1) % n + 1 == y) break;
      x += m;
    }
    
    printf("%d\n", x > nMaxDay ? -1 : x);
  }
  
  return 0;
}

int getGCD(int x, int y){
  if(x % y == 0) return y ;
  return getGCD(y, x % y);
}

int getLCM(int x, int y){
  int gcd = getGCD(x, y);
  return (x * y) / gcd;
}

주어진 해를 m으로 나눈 나머지가 x이면서 n으로 나눈 나머지가 y인 날을 찾되 mn의 최소공배수가 카잉 제국이 멸망하는 마지막 날이니 마지막 날을 초과하지 않을 때까지만 계산한다.


댓글을 달아 주세요