코영방

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=134&sca=10d0

#include<bits/stdc++.h>
using namespace std;
/*함수3 - 형성평가4
첫 번째는 1, 두 번째는 2, 세 번째부터는 앞의 두 수의 곱을 100으로 나눈 나머지로 이루어진 수열이 있다.
100 이하의 자연수 N을 입력받아 재귀함수를 이용하여 N번째 값을 출력하는 프로그램을 작성하시오.
입력 예
8
출력 예
92
*/
int d[1004];
int f(int n)
{
    int result;
    if(n==1) return 1;
    if(n==2) return 2;
    if(d[n]>0){
        return d[n];
    }
    else{
        d[n] = (f(n-1)*f(n-2))%100;
        return d[n];
    }
}

int main()
{
    int n,k;
    scanf("%d",&n);
    k=f(n);
    printf("%d",k);
	return 0;
}

https://www.acmicpc.net/problem/10816

upper bound와 lower bound을 구해서, "upper bound - lower bound" 하면 해당 검색 값의 개수를 구할 수 있다.

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,m,a[1000000]={0,},b[1000000]={0,},i,j,l,r,mid,cnt1=0,cnt2=0;
    scanf("%d",&m);

    for(i=0;i<m;i++)
        scanf("%d",&a[i]);
    scanf("%d",&n);
    for(j=0;j<n;j++)
        scanf("%d",&b[j]);

    //printf("222\n");
    sort(a,a+m);

    //printf("3333\n");
    l=0,r=m-1;
    for(j=0;j<n;j++)
    {
        //lower bound
        int lans = 0;
        while(l<=r)
        {
            mid=(l+r)/2;
            if(a[mid]==b[j])
            {
                lans = mid;
                r = mid-1;
            }
            else if(a[mid]>b[j])
                r=mid-1;
            else l=mid+1;

        }
        l=0,r=m-1;
        int uans = 0;
        while(l<=r)
        {
            mid=(l+r)/2;
            if(a[mid]==b[j])
            {
                uans = mid+1;
                l = mid+1;
            }
            else if(a[mid]>b[j])
                r=mid-1;
            else l=mid+1;

        }

        //if(l>r) printf("0 ");
        l=0,r=m-1;
        printf("%d ", uans-lans);
    }

    return 0;
}

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=226&sca=10d0

#include<stdio.h>
int k=0,c=1;
int f(int p)
{
	k=k+c;
	if(c==p)return k;
	c++;
	f(p);
}
int main()
{
	int n,x;
	scanf("%d",&n);
	x=f(n);
	printf("%d ",x);
	return 0;
}

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=227&sca=10d0

#include<bits/stdc++.h>
using namespace std;
vector<int> v;
void f(int n, int c)
{
	int i;
	if(v.size()==n){
		for(i=0; i<n; i++){
			printf("%d ",v[i]);
		}
		printf("\n");
		return;
	}
	for(i=c; i<=6; i++){
		v.push_back(i);
		f(n,i);
		v.pop_back();
	}
}
int main()
{
	int n;
	scanf("%d",&n);
	f(n,1);
	return 0;
}

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=228&sca=10d0

#include<bits/stdc++.h>
int f(int p)
{
	if(p==1)return 1;
	return f(p/2)+f(p-1);
}
int main()
{
	int i,k,n;
	scanf("%d",&n);
	k=f(n);
	printf("%d\n",k);
	return 0;
}

위 코드는 입력 값 n이 커지면, 상당히 느려진다.

그래서 아래와 같이 메모이제이션을 적용하였다.

#include<bits/stdc++.h>
int c[1004]={0,};
int f(int p)
{
	if(p==1){
		return 1;
	}
	else if(c[p]!=0){
		return c[p];
	}
	else{
		c[p]=f(p/2)+f(p-1);
	    return c[p];
	}
}
int main()
{
	int i,k,n;
	scanf("%d",&n);
	k=f(n);
	printf("%d\n",k);
	return 0;
}

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=235&sca=10e0

#include<bits/stdc++.h>
using namespace std;

int main()
{
    char n;
    while(1){
        scanf(" %c",&n);
        if(n>='A' && n<='Z'){
            printf("%c \n",n);
        }
        else if(n>='1' && n<='9'){
            printf("%d \n",n);
        }
        else break;
    }
	return 0;
}

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=131&sca=10d0

#include <bits/stdc++.h>
using namespace std;
/*
함수3 - 형성평가1
자연수 N을 입력받아 1부터 N까지 출력을 하되 n-1번째 값은 n번째 값을 2로 나눈 몫이 되도록 하는 프로그램을 작성하시오.
*/
void f(int n){
    if(n == 0) return;
    f(n/2);
    printf("%d ", n);
}

int main()
{
    int n;
    scanf("%d", &n);
    f(n);
    return 0;
}

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=132&sca=10d0

#include <bits/stdc++.h>
using namespace std;
/*
함수3 - 형성평가2
자연수 N을 입력받아 N이 홀수인 경우에는 1부터 N까지의 홀수를  짝수인 경우는 2부터 N까지의 짝수를 모두 출력하는 프로그램을 재귀함수로 작성하시오.
*/
void f(int n){
    if(n == 1 || n == 2){
        printf("%d ", n);
        return;
    }
    f(n-2);
    printf("%d ", n);
}

int main()
{
    int n;
    scanf("%d", &n);
    f(n);
    return 0;
}

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=216&sca=10c0

선택 정렬 사용해서 풀기,

가장 작은 값을 찾아서, 제일 오른쪽 끝으로 옮기는 방식으로 해결

#include <bits/stdc++.h>
using namespace std;
/*
함수2 - 자가진단 1
*/

void f(int a[], int n){ //int *b
    //내림차순

    int min;
    for(int i=0;i<n;i++)
    {
        min = 99;
        int min_idx = 0;
        for(int j=0;j<n-i;j++){
          if(min>a[j]){
            min=a[j];
            min_idx = j;
          }
        }
        int temp= a[min_idx];
        a[min_idx] = a[n-i-1];
        a[n-i-1] = temp;
    }
}

int main()
{
    int a[10];
    int n;
    scanf("%d",&n);

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

    f(a, n);  //배열의 이름은 배열의 시작 주소다.ㅁ

    for(int i=0;i<n;i++){
        printf("%d ", a[i]);
    }

    return 0;
}

위 코드에서  swap() 함수를 사용한 것으로 개선

https://en.cppreference.com/w/cpp/algorithm/swap

#include <bits/stdc++.h>
using namespace std;
/*
함수2 - 자가진단1
*/

void f(int a[], int n){ //int *b
    //내림차순

    int min;
    for(int i=0;i<n;i++)
    {
        min = 99;
        int min_idx = 0;
        for(int j=0;j<n-i;j++){
          if(min>a[j]){
            min=a[j];
            min_idx = j;
          }
        }
        /*
        int temp= a[min_idx];
        a[min_idx] = a[n-i-1];
        a[n-i-1] = temp;
        */
        swap(a[min_idx], a[n-i-1]);

    }
}

int main()
{
    int a[10];
    int n;
    scanf("%d",&n);

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

    f(a, n);  //배열의 이름은 배열의 시작 주소다.ㅁ

    for(int i=0;i<n;i++){
        printf("%d ", a[i]);
    }

    return 0;
}

선택 정렬 사용해서 풀기 2,

가장 큰 값을 찾아서, 제일 왼쪽 끝으로 옮기는 방식으로 해결

#include <bits/stdc++.h>
using namespace std;
/*
함수2 - 자가진단1
*/

void f(int a[], int n){ //int *b
    //내림차순

    int max;
    for(int i=0;i<n;i++)
    {
        max = -1000;
        int max_idx = 0;
        for(int j=i;j<n;j++){
          if(max<a[j]){
            max=a[j];
            max_idx = j;
          }
        }
        /*
        int temp= a[min_idx];
        a[min_idx] = a[n-i-1];
        a[n-i-1] = temp;
        */
        swap(a[max_idx], a[i]);

    }
}

int main()
{
    int a[10];
    int n;
    scanf("%d",&n);

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

    f(a, n);  //배열의 이름은 배열의 시작 주소다.ㅁ

    for(int i=0;i<n;i++){
        printf("%d ", a[i]);
    }

    return 0;
}

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=74&sca=10b0

#include <bits/stdc++.h>
using namespace std;
/*
함수1 - 형성평가4
*/

void f(void){
    int n;
    int a,b,c;
    for(int i=0;i<3;i++){
        //for(int j=0;j<3;j++){
            scanf("%d %d %d",&a,&b,&c);
            n=a+b+c;
            printf("%d %d %d %d \n",a,b,c,n);
        //}
        printf("\n");
    }
}

int main()
{


    f();

    return 0;
}

2번째 방법

3과목 점수도  for문을 사용해서 입력 받기

#include <bits/stdc++.h>
using namespace std;
/*
함수1 - 형성평가4
*/

void f(void){
    int n=0;
    int a,b,c;
    for(int i=0;i<3;i++){
        n=0;
        for(int j=0;j<3;j++){
            scanf("%d",&a);
            printf("%d-",a);
            n+=a;
        }

        printf("%d \n",n);

    }
}

int main()
{


    f();

    return 0;
}

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=73&sca=10b0

#include <bits/stdc++.h>
using namespace std;
/*
함수1 - 형성평가4
*/

int f(int a,int b){
    if(a>b){
        return (a*a)-(b*b);
    }
    else{
        return (b*b)-(a*a);
    }
}

int main()
{
    int a,b;

    scanf("%d %d",&a,&b);

    printf("%d ",f(a,b));

    return 0;
}

abs()함수 사용을 개선

https://en.cppreference.com/w/cpp/numeric/math/abs

#include <bits/stdc++.h>
using namespace std;
/*
함수1 - 형성평가4
*/

int f(int a,int b){
    /*
    if(a>b){
        return (a*a)-(b*b);
    }
    else{
        return (b*b)-(a*a);
    }
    */
    return abs((a*a)-(b*b));

}

int main()
{
    int a,b;

    scanf("%d %d",&a,&b);

    printf("%d ",f(a,b));

    return 0;
}

pow()함수 사용을 추가 개선

https://en.cppreference.com/w/cpp/numeric/math/pow

#include <bits/stdc++.h>
using namespace std;
/*
함수1 - 형성평가4
*/

int f(int a,int b){
    /*
    if(a>b){
        return (a*a)-(b*b);
    }
    else{
        return (b*b)-(a*a);
    }
    */
    return abs(pow(a,2)-pow(b,2));

}

int main()
{
    int a,b;

    scanf("%d %d",&a,&b);

    printf("%d ",f(a,b));

    return 0;
}

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=72&sca=10b0

#include <bits/stdc++.h>
using namespace std;
/*
함수1 - 형성평가3
*/

void f(int n){
    int i,j;
    for(i=1;i<=n;i++){
        for(j=i;j<=i*n;j=j+i){
            printf("%3d ",j);
        }
        printf("\n");
    }
}

int main()
{
    int i,j, n;

    scanf("%d",&n);

    f(n);
    return 0;
}

https://www.acmicpc.net/problem/10815

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,m,a[1000000]={0,},b[1000000]={0,},i,j,l,r,mid;
    scanf("%d",&m);

    for(i=0;i<m;i++)
        scanf("%d",&a[i]);
    
    scanf("%d",&n);
    for(j=0;j<n;j++)
        scanf("%d",&b[j]);

    //printf("222\n");
    sort(a,a+m);

    //printf("3333\n");
    l=0,r=m-1;
    for(j=0;j<n;j++)
    {
        while(l<=r)
        {
            mid=(l+r)/2;
            if(a[mid]==b[j])
            {
                printf("1 ");
                break;
            }
            else if(a[mid]>b[j])
                r=mid-1;
            else l=mid+1;

        }
        if(l>r) printf("0 ");
        l=0,r=m-1;
    }

    return 0;
}

https://www.acmicpc.net/problem/1463

#include <bits/stdc++.h>
using namespace std;

int main()
{
    long long int n,a[1000001]={0,},i;
    scanf("%lld",&n);

    for(i=2;i<=n;i++)
    {
        a[i]=a[i-1]+1;
        if(i%2==0 && a[i] > a[i/2] + 1)
            a[i] = a[i/2] + 1;
        if(i%3==0 && a[i] > a[i/3] + 1)
            a[i] = a[i/3] + 1;
    }

    /*
    for(i=1; i<=n; i++)
        printf("%lld : %lld  \n",i, a[i]);
        */
    printf("%d", a[n]);
    return 0;
}

https://www.acmicpc.net/problem/10819

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,a[1000000]={0,},max1=0,i,tmp=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    do
    {
        for(i=1;i<=n-1;i++)
        {
            tmp+=abs(a[i]-a[i+1]);
            if(max1<tmp)
            {
                max1=tmp;
            }
        }
        tmp=0;
    }while(next_permutation(a+1,a+n+1));
    printf("%d",max1);
    return 0;
}

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=225&sca=10d0

#include <bits/stdc++.h>
using namespace std;
/*
함수3 - 자가진단2
자연수 N을 입력받아 재귀함수를 이용하여 N부터 1까지 차례대로 출력하는 프로그램을 작성하시오.
N은 50이하의 자연수이다.

입력 예
5
출력 예
5 4 3 2 1
*/
void re(int p)
{
    printf("%d \n",p);
    if(p==1)return ;
    p--;
    re(p);
}

int main()
{
    int n;
    scanf("%d",&n);
    re(n);
    return 0;
}

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=224&sca=10d0

#include <bits/stdc++.h>
using namespace std;
/*
함수3 - 자가진단1
20 이하의 자연수 N을 입력받아 재귀함수를 이용해서 문자열 “recursive”를 N번 출력하는 프로그램을 작성하시오.
입력 예
3
출력 예
recursive
recursive
recursive
*/

void re(int p,int n)
{
    printf("recursive\n");
    if(p==n)return;
    p++;
    re(p,n);
}

int main()
{
    int n;
    scanf("%d",&n);
    re(1,n);
    return 0;
}

아래와 같이 수정했을때 , 출력 결과가 어떻게 나올지 생각해보면, 재귀함수 이해에 도움이 많이 될것 같네요.^^

#include <bits/stdc++.h>
using namespace std;
/*
함수3 - 자가진단1
20 이하의 자연수 N을 입력받아 재귀함수를 이용해서 문자열 “recursive”를 N번 출력하는 프로그램을 작성하시오.
입력 예
3
출력 예
recursive
recursive
recursive
*/

void re(int p,int n)
{
    printf("recursive %d   %d  \n", p, n);
    if(p==n)return;
    p++;
    re(p,n);
    printf("xxx %d   %d\n", p, n);
}

int main()
{
    int n;
    scanf("%d",&n);
    re(1,n);
    return 0;
}

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=81&sca=10c0

#include <bits/stdc++.h>
using namespace std;
/*
함수2 - 형성평가7
원주율을 3.141592로 매크로 상수로 정의하고 원의
넓이를 구하는 매크로 함수를 작성하여 반지름을 입력받아
원의 넓이를 출력하는 프로그램을 작성하시오. (소수 넷째자리에서 반올림)
입력 예
radius : 1.5
출력 예
area = 7.069
*/
#define PI 3.141592
#define AREA(r) r*r*PI
float f(float r)
{
    float s;
    //s=r*r*PI;
    s=AREA(r);
    return s;
}

int main()
{
    float r,k;
    printf("radius :");
    scanf("%f",&r);
    k=f(r);
    printf("area = %.3f",k);
    return 0;
}

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=80&sca=10c0

#include <bits/stdc++.h>
using namespace std;
/*
함수2 - 형성평가6
자료의 개수 7을 매크로 상수로 정의하여 자료의 개수만큼 정수를 입력받아 입력받은
순서대로 앞에서부터 마지막까지 가면서 바로 뒤의 숫자와 비교하여 크면 교환한다.
이러한 작업을 세 번 반복한 후 그 결과를 하나의 행에 공백으로 구분하여 출력하는 프로그램을 작성하시오.
입력 예
15 20 41 8 26 33 19
출력 예
8 15 20 19 26 33 41
*/
#define CNT 7
void f(int a[])
{
    int i,j;
    for(i=1; i<=3; i++){
        for(j=1; j<CNT; j++){
            if(a[j]>a[j+1]){
                swap(a[j],a[j+1]);
            }
        }
    }
}

int main()
{
    int i,a[1004];
    for(i=1; i<=CNT; i++){
        scanf("%d",&a[i]);
    }
    f(a);
    for(i=1; i<=CNT; i++){
        printf("%d ",a[i]);
    }
    return 0;
}

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=79&sca=10c0

#include <bits/stdc++.h>
using namespace std;
/*
함수2 - 형성평가5
세 개의 실수를 입력받아 합계와 평균을 구하여 평균을 반올림한 정수를 출력하고,
다음은 입력받은 수를 각각 먼저 반올림한 후 합계와 평균을 구하여 평균을 반올림한
한 결과를 출력하는 프로그램을 작성하시오.
입력 예
153.74 34.59 109.5
출력 예
99
100
*/

int f(float a,float b,float c)
{
    float x;
    x=(a+b+c)/3;
    x=round(x);
    return x;
}
int f2(float a,float b,float c)
{
     float y;
     y=(round(a)+round(b)+round(c))/3;
     y=round;
     return y;
}
int main()
{
    int k,k2;
    float a,b,c;
    scanf("%f %f %f",&a,&b,&c);
    k=f(a,b,c);
    k2=f2(a,b,c);
    printf("%d %d",k,k2);
    return 0;
}

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=78&sca=10c0

#include <bits/stdc++.h>
using namespace std;

/*
함수2 - 형성평가4
정수 n을 입력받아 2n의 값을 출력하는 프로그램을 작성하시오. (1 ≤ n ≤ 20)
입력 예
10
출력 예
1024
*/

int power(int a)
{
    int k=1,i;
    for(i=1; i<=a; i++){
        k=k*2;
    }
    return k;
}


int main()
{
    int a,f;
    scanf("%d",&a);
    f=power(a);
    printf("%d",f);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

/*
함수2 - 형성평가4
정수 n을 입력받아 2n의 값을 출력하는 프로그램을 작성하시오. (1 ≤ n ≤ 20)
입력 예
10
출력 예
1024
*/

int main()
{
    int a,f;
    scanf("%d",&a);
    f=pow(2,a);
    printf("%d",f);
    return 0;
}

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=77&sca=10c0

#include <bits/stdc++.h>
using namespace std;

/*
함수2 - 형성평가3
5개의 정수를 입력받아 각 정수의 절대값의 합을 출력하는 프로그램을 작성하시오.
입력 예
35 -20 10 0 55
출력 예
120
*/

void f(int a[])
{
    int i,c=0;
    for(i=1; i<=5; i++){
        c=c+abs(a[i]);
    }
    printf("%d",c);
}

int main()
{
    int i,a[1004];
    for(i=1; i<=5; i++){
        scanf("%d",&a[i]);
    }
    f(a);
    return 0;
}

https://www.acmicpc.net/problem/14002

아래 코드를 먼저 참고바랍니다.

https://coding-gongboo.tistory.com/38?category=829643

11053번 문제는 수열의 길이만 구하면 되지만, 14002문제는 수열을 표현해 주어야 한다.

#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
    int n,i,a[1000]={0,},l[1000]={0,},j,ma=-1,k[1000]={0,},m;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=1;i<=n;i++)
    {
        l[i]=1;
        k[i]=i;
        for(j=1;j<i;j++)
        {
            if(a[j]<a[i])
            {
                //l[i]=l[i]>l[j]+1 ? l[i] : l[j]+1;
                if(l[i] < l[j]+1)
                {
                    l[i] = l[j]+1;
                    k[i]=j;
                }
            }
        }
       // ma=ma>l[i]?ma:l[i];
        if(ma<l[i]){
            ma=l[i];
            m=i;
        }
    }
    printf("%d\n",ma);
    l[1] = a[m];
    for(i=2;i<=ma;i++)
    {
        l[i]=a[k[m]];
        m = k[m];
    }
    for(i=ma;i>0;i--)
        printf("%d ",l[i]);
    return 0;
}

https://www.acmicpc.net/problem/11053

이문제는 LIS(Longest Increasing Subsequence) 라는 유명한 문제입니다.

아래 코드는 다이내믹 방식으로 소스코드를 작성했습니다.

참고하시구요. 질문이나 수정할 부분있으면 알려주세요.^^

#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
    int n,i,a[100000]={0,},l[100000]={0,},j,ma=-1;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=1;i<=n;i++)
    {
        l[i]=1;
        for(j=1;j<i;j++)
        {
            if(a[j]<a[i])
                l[i]=l[i]>l[j]+1 ? l[i] : l[j]+1;
        }
        ma=ma>l[i]?ma:l[i];
    }
    printf("%d",ma);
    return 0;
}

문제는 아래 첨부 파일 참고하세요.

등수의 범위를 알고자 하는 학생(x)을 기준으로, 

- 확실히 등수가 높은 학생 리스트 (아래 코드에서 up vector, x학생 포함)

- 확실히 등수가 낮은 학생 리스트 (아래 코드에서 down vector, x학생 포함)

아래 소스코드는 up/down vector에 학생 번호가 중복되어 있으면 삭제해서, unique(유일하게) 하는 코드 입니다.

    sort(up.begin(), up.end());
    up.erase(unique(up.begin(), up.end()), up.end());

    sort(down.begin(), down.end());
    down.erase(unique(down.begin(), down.end()), down.end());

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, x;
    vector<int> up;
    vector<int> down;

    scanf_s("%d %d %d", &n, &m, &x);
    int input[1000000][2];

    for (int i = 0; i < m; i++) {
        scanf_s("%d %d", &input[i][0], &input[i][1]);
    }

    up.push_back(x);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < up.size(); j++) {
            if (input[i][1] == up[j]) {
                up.push_back(input[i][0]);
            }
        }
    }
    down.push_back(x);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < down.size(); j++) {
            if (input[i][0] == down[j]) {
                down.push_back(input[i][1]);
            }
        }
    }

    sort(up.begin(), up.end());
    up.erase(unique(up.begin(), up.end()), up.end());

    sort(down.begin(), down.end());
    down.erase(unique(down.begin(), down.end()), down.end());


    printf("%d %d", up.size(), n - down.size()+1);
    return 0;
}

문제는 아래 첨부 파일은 참고하세요.^^

2019년 정올 2차 - 초등 1번 문제

#include<bits/stdc++.h>
using namespace std;

int main() {
    int i,m,n,l,c1,k=0;
    scanf("%d",&n);
    for(i=1; i<=n; i++){
        m=i;
        for(l=1000000; l>=1; l/=10){
            c1=m/l;
            m=m-c1*l;
            if(c1==3 || c1==6 || c1==9){
                printf("%d\n", i);
                k++;
                c1=0;
            }

        }
    }
    printf("%d",k);
    return 0;
}

2019 정올 2차 초등 1번 - 풀이방법 2

#include<bits/stdc++.h>
using namespace std;

int main() {
    int i,m,n,l,c1,k=0;
    scanf("%d",&n);
    for(i=1; i<=n; i++){
        m=i;
        while(m != 0){
            int mod = m%10;
            if(mod==3 || mod==6 || mod==9)k++;
            m=m/10;
        }
    }
    printf("%d",k);
    return 0;
}

https://www.acmicpc.net/problem/2529

문제의 조건이 순서만 변경할 수 있을 때는 순열을 사용하면 됩니다.

부등호 앞에 그리고 뒤에 한 자리 숫자를 나와서 모든 부등호의 관계를 만족시키려고 합니다

하지만 이때 선택한 수가 같으면 안 됨.

문제의 가장 중요한 조건 중에 하나는 선택할 숫자는 한자리숫자 이고 선택한 숫자가 같은면 안된다.

즉, 순서 문제가 된다.

예를 들어, 0부터 9까지 소중해서 일정 4개를 골랐다고 해봅시다. 그럼 9,8,7,6 을 선택해서, 중복없이 순서대로 나열하고, 부등호가 성립되는지 확인하면된다.

<전체 경우의 수>

10개의 수중에 K+1개를 고른다 = 2^(k+1)  --> 필요없음.

이 K+1개의 수에 대해서 순서를 정한다. = !(K+1)

부등호가 성립하는 검사 = K+1

결론 : 2^10 * 10! * 10 = 1024 * 3628800*10 (OMG)

자~!! 시간복잡도를 줄여 봅시다.

가장큰수와 가장작은수를 찾는 것임으로, K+1이 4개라면,

큰수는 9,8,7,6 작은수는 0,1,2,3 을 선택하면 된다.

즉, 위 시간복잡도에서 2^(K+1)이 없어지게 된다.

#include <bits/stdc++.h>
using namespace std;
bool check(vector<int>& perm, vector<char>& a);

int main() {
    int k;
    cin >> k;
    vector<char> a(k);
    vector<int> min(k + 1);
    vector<int> max(k + 1);
    for (int i = 0; i < k; i++) {
        cin >> a[i];
    }

    for (int i = 0; i <= k; i++) {
        min[i] = i;
        max[i] = 9 - i;
    }
    do {
        if (check(min, a)) {
            break;
        }
    } while (next_permutation(min.begin(), min.end()));
    do {
        if (check(max, a)) {
            break;
        }
    } while (prev_permutation(max.begin(), max.end()));
    for (int i = 0; i < max.size(); i++) {
        cout << max[i];
    }
    cout << '\n';
    for (int i = 0; i < min.size(); i++) {
        cout << min[i];
    }
    cout << '\n';
    return 0;
}

bool check(vector<int>& perm, vector<char>& a) {
    for (int i = 0; i < a.size(); i++) {
        if (a[i] == '<' && perm[i] > perm[i + 1]) {
            return false;
        }
        if (a[i] == '>' && perm[i] < perm[i + 1]) {
            return false;
        }
    }
    return true;
}

https://www.acmicpc.net/problem/1697

BFS를 사용해서 쉽게풀수 있는 문제다.

BFS는 아래그림과 같이 그래프 순회방법중의 하나이다.

특히, BFS는 간선의 가중치가 모두 동일한 경우, 최단거리와 같은 최소비용 문제를 해결하기에 적합합니다.

아래 그래는 Graph의 표현 방법과 순회에 대해서 대략적으로 요약한 것이니 참고하시기 바랍니다.

인접리스트의 경우 실제 리스트를 사용하기 보다는 보통 vector를 사용해서 해결하는 경우 많으니 참고하세요.

아래 BFS의 슈도코드라고 할까요? 대략적인 알고리즘을 확인 하실수 있겠습니다.

자~!! 이제 본 숨바꼭질 문제의 풀이 방법입니다. 아래 그림을 통해 찬찬히 고민해보시기 바랍니다.

수빈이의 위치 X에서 1초후에 이동할 수 있는 곳은 X-1, X+1, X*2 입니다. 어떤 이동방법을 선택하더라도 1초가 걸리니까, 이것은 모든 간선의 가중치가 1초라고 보면 되겠네요.^^

그리고X-1을 할때는 X-1이 0보다 작으면 중단하면 되겠죠.

X+1, X*2의 경우는 다음 위치가 200,000보다 작거나 같은때만 처리해주면 되겠네요.^^

많은 도움되셨길바라며, 아래 소스코드 참고하세요.^^

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,k,c[200005]={0,},v[200005]={0,},t;
    queue <int> q;
    scanf("%d %d",&n,&k);
    v[n]=1;
    c[n]=0;
    q.push(n);
    while(!q.empty())
    {
        t=q.front();
        q.pop();
        if(t-1 >= 0 && v[t-1]==0){
            q.push(t-1);
            c[t-1]=c[t]+1;
            v[t-1] = 1;
        }
        if(t+1 < 200000 && v[t+1]==0){
            q.push(t+1);
            c[t+1]=c[t]+1;
            v[t+1] = 1;
        }
         if(t*2 < 200000 && v[t*2]==0){
            q.push(t*2);
            c[t*2]=c[t]+1;
             v[t*2]=1;
        }
        //v[t-1]=v[t+1]=v[t*2]=1;
    }
    printf("%d",c[k]);
    return 0;
}

https://www.acmicpc.net/problem/11727

전형적인 다이내믹 (동적계획법)문제다.

점화식은 아래 스케치를 참고하세요.^^

점화식 : K(n) = K(n-1) + 2*K(n-2)

<Top-Down - 재귀함수 사용 방법>

#include<bits/stdc++.h>
using namespace std;

int d[1001];

int tile(int n)
{
    if(n < 2) return 1;
    if(d[n] > 0) return d[n];
    
    d[n] = (tile(n-1) + tile(n-2) + tile(n-2))%10007;
    return d[n];
}
int main() {

    int n;
    scanf("%d",&n);

    printf("%d\n",tile(n));
    return 0;
}

<Bottom-Up>

#include<stdio.h>
int k[1004];
int main()
{
	int n,i,j;
	scanf("%d",&n);
	for(i=1; i<=1004; i++)k[i]=0;
	k[1]=1;
	k[2]=3;
	for(i=3; i<=n; i++){
        k[i]=k[i-1]+k[i-2]*2;
	}
	printf("%d",k[n]%10007);
	return 0;
}

https://www.acmicpc.net/problem/10818

최대값, 최솟값을 구할때는 해당 문제에서 입력가능한 범위를 확인해야 한다.

입력 범위보다 작은 값은 최대값에 해당하는 변수의 초기값으로 사용하고,

입렵 범위보다 큰값을 최솟값에 사용할 변수의 초기값으로 사용해야 한다.

#include<stdio.h>

int main()
{
    int max=-1000001,min=1000001,n,k;

    scanf("%d",&n);

    for(int i=0;i<n;i++)
    {
        scanf("%d",&k);
        if(k>max)
        {
            max=k;
        }
        if(k<min)
        {
            min=k;
        }
    }
    printf("%d %d",min,max);
    return 0;

}