코영방

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

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

int rec(int mul, int n){
    if(n == 0)
        return mul;
    int t = n%10;
    if( t != 0){
        mul *= t;
    }
    return rec(mul, n/10);
}
int main() {
    int a,b,c;
    cin >> a >> b >> c;
    int n = a * b * c;

    printf("%d ",rec(1, n));

    return 0;
}

#include <bits/stdc++.h>
using namespace std;
//숫자삼각형 (종류3)
int main()
{
    int n;
    cin >> n;
    int x;

    int a[100][100];
    fill(&a[0][0], &a[99][100], -1);


    int p = 1;
    for(int i=0; i<2*n-1; i++){
        for(int j=0; j<p; j++){
            a[i][j] = j+1;
        }
        if(i<n/2){
            p++;
        }
        else{
            p--;
        }
    }

    for(int i=0; i<2*n; i++){
        for(int j=0; j<n; j++){
            if(a[i][j] == -1){
                cout << " ";
            }
            else{
                cout << a[i][j];
            }

        }
        cout << "\n";
    }
    return 0;
}

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

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/*
5 1 5
1 2 1
2 3 2
3 4 3
4 5 4
*/
int vi[100010],max1,tot;
vector <pair<int,int>> v[100010];

void dfs(int s, int e, int lmax, int l)
{
    if(s==e) {
        max1=lmax;
        tot=l;
    }
    else{
        vi[s]++;
        for(int i=0;i<v[s].size();i++)
        {
            if(vi[v[s][i].first]==0)
            {
                int last=lmax>v[s][i].second?lmax:v[s][i].second;
                dfs(v[s][i].first,e,last,l+v[s][i].second);
            }
        }
    }

}
int main()
{
    int r,r1,r2,i,s,e,d;

    scanf("%d %d %d",&r,&r1,&r2);
    for(i=1;i<r;i++)
    {
        scanf("%d %d %d",&s,&e,&d);
        v[s].push_back(make_pair(e,d));
        v[e].push_back(make_pair(s,d));
    }
    dfs(r1,r2,0,0);
    printf("%d",tot-max1);
    return 0;
}

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

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

int sum; 
void Div_sum(int num)
{
    if(num == 0)
    {
        return;
    }

    sum+=(num%10);
    Div_sum(num/10);
}

int main(void)
{
    int n;
    int cnt=0;
    scanf("%d", &n);

    for(int i=1; i<=n; i++)
    {
        Div_sum(i);
        if((i%sum) == 0)
        {
            cnt++;
        }
        sum = 0;
    }

    printf("%d", cnt);

    return 0;
}

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

int main() {
  int a;
  cin >> a;
  int cnt = 0;
  for(int i=1; i <=a; i ++)
  {
    int sum = 0;
    int temp = i;
    while(temp){
      sum = sum + temp%10;
      temp = temp / 10;
    }
    //cout << "== " << sum << "\n";
    if( i % sum == 0) cnt ++;
  }

  cout << cnt;
  
}

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

#include <bits/stdc++.h>
using namespace std;
/*
583 : 함수2 - 자가진단5
세 개의 실수를 입력받아
가장 큰 수를 올림한 정수를 출력하고
가장 작은 수를 내림한 정수를 출력한 후
남은 수를 반올림한 정수를 출력하는 프로그램을 작성하시오.
입력되는 실수는 -1000이상 1000이하이다.
입력 예
3.45 51.48 -100.1
출력 예
52 -101 3
*/
bool comp(int a,int b){
     return a>b;
}

int main()
{
    float a[3];
    for(int i= 0;i<3;i++){
        scanf("%f",&a[i]);
    }
    float max,mid,min;

    sort(a, a+3,comp);

    max=a[0];
    mid=a[1];
    min=a[2];

    printf("%.2f %.2f %.2f",ceil(max),round(mid),floor(min));

    return 0;
}

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

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

int check_sum(int n, int m){
    //v의 총합 이 M인지 확인
    int x=0;
    for(int i=0; i<n; i++){
        x=x+v[i];
    }
    if(x==m)return 1;
    else return 0;
}

void f(int n, int m)
{
    int i;
    //printf("=== %d \n", v.size());
    if(v.size()==n){
        if(check_sum(n,m)==1){
            //printf("===0");
            for(i=0; i<n; i++){
                printf("%d ",v[i]);
            }
            printf("\n");
            return;
        }
        else return;
    }

    for(i=1; i<=6; i++){
        v.push_back(i);
        f(n,m);
        v.pop_back();
    }
}


int main()
{
    int n,m;
    //printf("==== 0");
    scanf("%d %d",&n,&m);
    //printf("==== 1")
    f(n,m);
	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;
}

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;
}

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

등수의 범위를 알고자 하는 학생(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/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;
}

정올 기출 풀이는 좀 조심스럽긴 하다....

아직 정올 기출풀이에 대해서 유료 교육 컨텐츠라고 볼 수 있을듯해서다....

처음 정올 교육을 시작한 2010년도 문제부터 최근 문제까지 나름의 문제풀이 방식을 공유해보려 한다.

기대하시라~!!!ㅋ

지난 몇개월 동안 백준 문제풀이 사이트에서 딱 204개의 문제를 풀어봤다. 

2020년도 안에 300문제정도를 더 풀어서 백준사이트 랭킹 1000등안에는 들어가볼 계획이다.

내가 직접푼 소스코드는 물론이고, 학생들과 공부하는 과정에서 얻은 주옥같은 코드들도 공유하려한다.

대한민국이 SW강국이 되는 그날을 기대하며.......

https://www.acmicpc.net/