늅늅이라도 코딩이 하고싶어

2798 블랙잭

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

이번 문제는 간단히 수열 중 3개의 값의 합이 m을 넘지 않으면서 가장 m에 근사한 합을 찾아내는 문제이다.

간단히 브루트포싱하여 풀 수 있었다.

#include <stdio.h>
#include <algorithm>
int main()
{
    int i,j,k,n,m,arr[101],s,t=-1;
    scanf("%d %d", &n, &m);
    for(i=0; i<n; i++) {
        scanf("%d", &arr[i]);
    }
    std::sort(arr, arr+n);
    for(i=0; i<n-2; i++) {
        for(j=i+1; j<n-1; j++) {
            for(k=j+1; k<n; k++) {
                s=arr[i]+arr[j]+arr[k];
                if(m==s) {
                    printf("%d",s);
                    return 0;
                }
                else if(m-s>0) {
                    if(s>t) t=s;
                }
                else k=n;
            }
        }
    }
    printf("%d", t);
}

1149 RGB거리

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

이번 문제는 간단한 DP문제이다.

이 마을에서는 빨강, 초록, 파랑색으로 페인트 칠을 한다.

i번째 사람은 이웃한 i-1번째와 i+1번째의 사람과 같은 색을 사용할 수 없다.

각 집들의 빨강, 초록, 파랑색을 칠했을 때 사용되는 요금이 있을 때, 전체 비용의 최소 비용을 구하면 된다.

그래서 단순히 DP1, DP2, DP3에 각 비용을 입력받고 그걸 기반으로 계산하는 점화식을 세웠다.

DP1[i]+=min(DP2[i-1],DP3[i-1]);

DP2[i]+=min(DP1[i-1],DP3[i-1]);

DP3[i]+=min(DP1[i-1],DP2[i-1]);

로 간단히 반복적 DP를 세우고, 세 DP[n] 값에서 최소값을 출력하였다.

#include <stdio.h>
#include <algorithm>

using namespace std;

int main()
{
    int n,i;
    scanf("%d", &n);
    int dp1[1001],dp2[1001],dp3[1001];
    for(i=1; i<=n; i++) scanf("%d %d %d", &dp1[i], &dp2[i], &dp3[i]);
    for(i=2; i<=n; i++) {
        dp1[i]+=min(dp2[i-1],dp3[i-1]);
        dp2[i]+=min(dp1[i-1],dp3[i-1]);
        dp3[i]+=min(dp1[i-1],dp2[i-1]);
    }
    printf("%d", min(min(dp1[n],dp2[n]),dp3[n]));
}

12091 이브이 진화 시키기

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

오랫만에 참신하고 재밌던 문제였다.

문제 내용은 이브이는 샤미드(Vaporeon), 쥬피썬더(Jolteon), 부스터(Flareon) 중의 하나로 진화한다.

유저가 제출을 할 때 마다 채점 프로그램은 이브이 세 마리를 진화시킨다.

채점 프로그램은 운이 좋기 때문에, 이브이의 진화 결과는 샤미드, 쥬피썬더, 부스터 한 마리씩 진화한다.

진화하지 못하는 경우는 없다.

뭐 대충 이런 문제여서 그냥 운으로 찍는 스페셜 저지 문제인 줄 알았다.

하지만 힌트를 보아하니 '이 문제를 올바르게 보려면 자바스크립트가 필요합니다.' 라는 내용이 보였다.

그래서 JS를 뜯어보니, 하단에 이런 코드를 발결할 수 있었고, 이걸 기반으로 푸는 문제였다.

보아하니 3으로 나눈 나머지 진화한 값을 출력하는 것이다.

이런식으로 문제를 내는 걸 본 것은 처음이라 재밌었다.

#include <stdio.h>
int main()
{
    int n;
    char str[3][10]={"Vaporeon", "Jolteon", "Flareon"};
    scanf("%d", &n);
    printf("%s", str[++n%3]);
}

1032 명령 프롬포트

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

이 문제는 cmd의 dir을 쳐서 서브디렉토리 파일에서 원하는 파일을 찾기위한 문제이다.

간단히 dir 패턴과 같이 쳐서 그 패턴에 맞는 파일만 검색 결과로 나온다.

그래서 dir a?b.exe라는건 ?위치에는 아무거나 들어가고 첫 번째 글자는 a, 세 번째 글자는 b라는 것이다.

이 문제는 검색 결과가 먼저 주어졌을 때, 패턴으로 뭘 쳐야그 결과가 나오는지 출력하는 문제다.

패턴에는 알파벳과 ".", "?"만 넣을 수 있다.

그리고 가능하다면 ?를 적게 써야한다.

간단히 첫번째 입력을 저장시켜놓고, 다음줄부터 들어오는 입력과의 차이가 나는 부분을 "?"로 바꾸면 되는 문제이다.

#include <stdio.h>
int main()
{
    int n,i,j;
    char str[51],st[51];
    scanf("%d", &n);
    scanf("%s", str);
    for(i=1; i<n; i++) {
        scanf("%s",st);
        for(j=0; st[j]; j++) {
            if(str[j]!=st[j]) str[j]='?';
        }
    }
    printf("%s",str);
}

1026 보물

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

이번 문제는 간단한 탐색 정렬문제이다.

S=A[0]*B[0]+A[1]*B[1]...A[n-1]*B[n-1] 의 수열값이 존재하며, B의 수열은 고정, A의 수열을 재배열하여 S의 최소값을 만드는 문제이다.

시간복잡도가 O(n^2)이 나오겠지만 귀찮으니 하드코딩하여 풀었다.

단순히 B의 최대값을 탐색, A의 최소값과 매치, B의 최대값의 위치를 체크, 체크 안된 다음 최대값을 탐색, 그리고 다시 매치하여 단순 탐색 정렬로 풀었다.

#include <stdio.h>
#include <algorithm>
int main()
{
    int i,j,n,s=0,a[51],b[51],c[51],d[51]={0},maxi,wherem;
    scanf("%d", &n);
    for(i=0; i<n; i++) scanf("%d", &a[i]);
    for(i=0; i<n; i++) scanf("%d", &b[i]);
    std::sort(a,a+n);
    for(i=0; i<n; i++) {
        maxi=-1;
        wherem=-1;
        for(j=0; j<n; j++) {
            if(!d[j] && maxi<b[j]) {maxi=b[j];wherem=j;}
        }
        d[wherem]=1;
        c[wherem]=a[i];
    }
    for(i=0; i<n; i++) s+=c[i]*b[i];
    printf("%d",s);
}

14624 전북대학교

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

전북대학교의 심볼은 균형과 조화, 지성과 이상을 향한 방향성과 목표를 나타낸다.

절제된 한국적 아름다움을 꾸밈없는 소박함과 여백을 통해 시각화하였으며, 심볼의 방향에 따라 한국적인 대학, 학문에 정진하는 대학, 미래로 나아가는 대학의 의미를 포함하여 ‘성장을 넘어 성숙의 대학으로 나아가는 전북대학교’의 철학과 비전을 상징한다.

가 이번 문제의 내용이다.

홀수가 입력되면 전북대학교 심볼모양의 별찍기를 하고, 짝수가 입력되면 I LOVE CBNU를 출력한다.

#include <stdio.h>
int main()
{
    int n,i,j,r;
    scanf("%d", &n);
    if(n%2) {
        for(i=0; i<n; i++) printf("*");
        puts("");
        n/=2;
        r=n;
        for(i=0; i<r; i++) printf(" ");
        puts("*");
        for(i=1; i<=n; i++) {
            for(j=1; j<r; j++) printf(" ");
            r--;
            printf("*");
            for(j=0; j<i*2-1; j++) printf(" ");
            puts("*");
        }
    }
    else puts("I LOVE CBNU");
}

15947 아기 석환 뚜루루 뚜루

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

이번 문제는 단순 출력 문제로, 노래를 부르면서 tururu와 turu 구절에 ru를 추가하면서 부르는 조건으로 n번째 부른 단어를 출력하면 된다.

그리고 k번째 반복 될 때, k>=5라면 "tu+ru*k" 형식으로 출력한다.

귀찮아서 하드코딩했다.

대충 만든거다보니 영 좋은 코드는 아닌 듯 하다.

그냥 푼 김에 올려본다.

#include <stdio.h>
int main()
{
    int n,k,i;
    char str[15][9]={" ","baby","sukhwan","tururu","turu","very","cute","tururu","turu","in","bed","tururu","turu","baby","sukhwan"};
    scanf("%d", &n);
    k=n/14;
    n%=14;
    if(!n) n=14;
    if(!(n%4) || !((n-3)%4)) {
        if(k>2 && !((n-3)%4)) printf("tu+ru*%d",k+2);
        else if(k>3 && !(n%4)) printf("tu+ru*%d",k+1);
        else {
            printf("%s",str[n]);
            for(i=0; i<k; i++) printf("ru");
        }
    }
    else printf("%s", str[n]);
}

2309 일곱 난쟁이

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

이번 문제는 단순히 무차별 대입으로 풀 수 있는 문제이다.

일곱 난쟁이들 중 가짜 난쟁이들이 껴서 아홉 난쟁이가 되었는데, 이 중 진짜 일곱 난쟁이를 찾아야한다.

백설 공주는 다행히도 일곱 난쟁이의 키의 합이 100이라는 사실을 알고있다.(그런건 외우는데 왜 얼굴을 못외웠을까)

일곱 난쟁이의 키의 합은 100이므로, 진짜 일곱 난쟁이를 찾은 후 해당되는 일곱 난쟁이의 키들을 출력하는 문제이다.

그래서 단순히 선택정렬스럽게 브루트 포스하였다.

#include <stdio.h>
#include <algorithm>
int main()
{
    int arr[9],i,j,k,x,y,s;
    for(i=0; i<9; i++) scanf("%d", &arr[i]);
    for(i=0; i<8; i++) {
        for(j=i+1; j<9; j++) {
            s=0;
            x=i;y=j;
            for(k=0; k<9; k++) {
                if(k!=x && k!=y) {
                    s+=arr[k];
                }
            }
            if(s==100) {
                arr[x]=-1;
                arr[y]=-1;
                std::sort(arr,arr+9);
                for(k=2; k<9; k++) printf("%d\n",arr[k]);
            }
        }
    }
}

1806 부분합

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

이번 문제도 간단한 DP다.

단순히 부분 수열의 합이 S 이상 되는 것의 최소 길이를 출력하는 문제이다.

그래서 나는 DP[i]+=DP[i-1] 로 부분 수열들을 만들어놓고, DP[i]에서 DP[j]를 빼면서 수열의 길이별로 비교를 해보았다.

그 중에서 처음 S 이상의 합을 만족하는 가중치 t를 잡아놓았다면, 그 이하길이의 부분 수열은 합이 S를 넘을 수 없기 때문에 그냥 체크하지 않았다.

그리고 S 이상의 합을 만족하는 부분 수열이 체크될 때마다 길이를 비교하여 최소 길이를 구했다.

#include <stdio.h>
#include <stdlib.h>
int main()
{
    int n,s,r=0,i,j,t=0,k;
    long long int* DP;
    scanf("%d %d", &n, &s);
    DP=(long long int*)calloc(n+1,sizeof(long long int));
    for(i=1; i<=n; i++) {
        scanf("%lld", &DP[i]);
        DP[i]+=DP[i-1];
        if(DP[i]>=s && !r) {
            t=i;
            r=1;
        }
    }
    if(!t) {printf("0");return 0;}
    int MIN=t;
    for(i=t; i<=n; i++) {
        k=0;
        for(j=i-1; j>0; j--) {
            if(DP[i]-DP[j]>=s && !k) {
                r=0;
                if(MIN>i-j) MIN=i-j;
                k=1;
            }
            else if(k) j=-1;
        }
    }
    printf("%d", MIN);
}

10844 쉬운 계단 수

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

이번 문제는 쉬운 계단 수, 쉬운 계단 수란 자릿수마다 인접한 수들의 차이가 1만 차이가 난다.

즉, 4565456, 1234, 5654 같은 수는 쉬운 계단 수이다.

11이나 14, 1235 같은 수는 쉬운 계단 수가 아니다.

n자리수 숫자 중 쉬운 계단 수의 개수를 구해서 10억으로 나눠서 출력하는 문제이다.

n=1

1 2 3 4 5 6 ...

n=2

10 12 21 23 43 45 54 56 ...

대충 생각해보니, n자리수의 숫자는 n-1자리수에 인접한수 +-1만큼의 차가 난다.

즉, DP[i][j]=DP[i-1][j-1]+DP[i-1][j+1] 인 셈이다.

참고로 0의 경우는 인접한 수를 저렇게 계산하면 -1을 세기때문에 말이 안된다.

따라서 DP[i][0]=DP[i][1] 이 좋을 것이다.

9의 경우도 10을 세면 안되므로, 배열의 초기 크기를 11로 만들고 10번째 배열에 0을 넣어두면 될 것이다.

그렇게 해서 풀었는데, 처음에 풀때, 합 계산할 때 나누는 것을 생각하지 못한 탓에 내 시간이 20분 증발했다. (정말 쓸데없는데서 틀렸었다니 풀고나서 기분나빴다.)

#include <stdio.h>
int main()
{
    int n,i,j;
    long long int DP[101][11]={0},s=0;
    for(i=1; i<=9; i++) DP[0][i]=1;
    scanf("%d", &n);
    for(i=1; i<n; i++) {
        DP[i][0]=DP[i-1][1];
        for(j=1; j<=9; j++) DP[i][j]=(DP[i-1][j-1]+DP[i-1][j+1])%1000000000;
    }
    for(i=0; i<=9; i++) {s+=DP[n-1][i];s%=1000000000;}
    printf("%lld",s);
}