[TIL]20210719

알고리즘

백준 2292

 #include <stdio.h>
#include <string.h>
int main()
{
  int n,circle=1;
  scanf("%d",&n);
  if (n==1){
    printf("1");
  }
  else{
    n=n-1;
    while(1){
      n=n-circle*6;
      if (n<=0){
        break;
      }
      circle++;

    }
  printf("%d",circle+1);

  }
}

백준 1193

 #include <stdio.h>
#include <string.h>
int main()
{
  int index=0,sum,nut,num_1;
  scanf("%d",&nut);
  while (1){
    index++;
    sum=index*(index+1)/2;
    if(nut<=sum){
      break;
    }
  }

  num_1=nut-(index-1)*index/2;

  if(index%2==0){
    printf("%d/%d",num_1,index-num_1+1);
  }
  else{
    printf("%d/%d",index-num_1+1,num_1);
  }
}

문제가 어렵다. 인터넷을 참고하여 이해했다.
(1/1), (1/2, 2/1) 이런식으로 대각선을 기준으로 index(섹션느낌)으로 나눌 수 있다. 그리고 이 index 숫자는 각 섹션의 최댓값이라고도 볼 수 있다. 여기서의 규칙성은 순,역방향을 고려하지 않았을때 분자와 분모는 한칸당 1씩차이나는 등차수열로 볼 수 있다.
num_1 변수는 해당 섹션 바로 이전 섹션까지의 갯수 총합을 구해 스캔한 값이 섹션에서 몇번째 값인지를 구한다. 이 값이 분자 또는 분모가 되고 index에서 빼버리고 1을 더한다면 나머지 분자 또는 분모가 된다.

백준 2869

#include <stdio.h>
#include <string.h>
int main()
{
  int V,A,B,day=0;
   scanf("%d %d %d",&A,&B,&V);
  day=(V-B)/(A-B);
  if((V-B)%(A-B) != 0){
  printf("%d",day+1);
  }
  else{
  printf("%d",day);
   
  }
}

이 문제또한 무턱대고 while과 break를 쓸 수 없다. 미리 계산식을 만들어서 출력해줘야한다.

백준 10250

#include <stdio.h>
#include <string.h>
int main()
{
  int num,H,W,N;
  scanf("%d",&num);
  for (int i = 0;i<num;i++){
    int cnt=0;
    scanf("%d %d %d",&H,&W,&N);
    for (int j=1;j<W+1;j++){
      for (int k=1;k<H+1;k++){
        cnt++;

        if (cnt==N){

          if (j<10){
          printf("%d0%d\n",k,j);
          }
          else{
          printf("%d%d\n",k,j);
          }
        break;
        }
      }
    }
  }
}

백준 2775

#include <stdio.h>
#include <string.h>
int main()
{
  int a[15][15]={0},K,N,cnt;
  //k층 n호
  for (int i=0;i<15;i++){
    a[0][i]=i;
  }
  for (int i=1;i<15;i++){
    for (int j=1;j<15;j++){
      a[j][i]=a[j-1][i]+a[j][i-1];
    }
  }

  scanf("%d",&cnt);
  for (int i=0;i<cnt;i++){
  scanf("%d",&K);
  scanf("%d",&N);
  printf("%d\n",a[K][N]);
  }
}