백준 새싹 배지 얻기 - 1월 넷째 주

1/23. 별 찍기 - 4 (백준 2441번)

 

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

 

//C
#include <stdio.h>

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

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i; j++)
            printf(" ");
        for (int j = 0; j < n-i; j++)
            printf("*");
        printf("\n");
    }

    return 0;
}

 

오늘은 브론즈3으로 간단하게 슝- (정답)

 

---

 

1/24. 별 찍기 - 2 (백준 2439번)

 

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

 

//C
#include <stdio.h>

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

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n-i-1; j++)
            printf(" ");
        for (int j = 0; j <= i; j++)
            printf("*");
        printf("\n");
    }

    return 0;
}

 

오늘도 간단한 문제 슝- (정답) 연휴니까... 힛,, 아 그리고 드디어 실버 등극!!! 우앙!!!

 

---

 

1/25. 기타줄 (백준 1049번)

 

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

 

//C
#include <stdio.h>

int main()
{
    int n, m;
    int set[50] = {0}, each[50] = {0};
    scanf("%d %d", &n, &m);

    int setmin = 1000, eachmin = 1000;
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d", &set[i], &each[i]);

        if (set[i] < setmin)
            setmin = set[i];
        
        if (each[i] < eachmin)
            eachmin = each[i];
    }

    if (setmin >= eachmin * 6)
    {
        int ans = n * eachmin;
        printf("%d\n", ans);
    }
    else
    {
        int setnum = n / 6;
        int eachnum = n % 6;

        int ans1 = setnum * setmin + eachnum * eachmin;
        int ans2 = (setnum + 1) * setmin;

        if(ans1 < ans2)
            printf("%d\n", ans1);
        else
            printf("%d\n", ans2);
    }

    return 0;
}

 

(정답)

 

---

 

1/26. 피보나치 함수 (백준 1003번)

 

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

 

//C
#include <stdio.h>

int fibo[50];

void initialize()
{
    fibo[0] = 0;
    fibo[1] = 1;
}

int fibonacci(int n)
{
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else
    {
        for (int i = 2; i <= n; i++)
        {
            fibo[i] = fibo[i-1] + fibo[i-2];
        }
        return fibo[n];
    }
}

int main()
{
    initialize();
    
    int t;
    int n[40], num0[40], num1[40];

    scanf("%d", &t);
    for (int i = 0; i < t; i++)
    {
        int n, num0, num1;
        
        scanf("%d", &n);

        if (n == 0)
        {
            num0 = 1;
            num1 = 0;
        }
        else
        {
            num0 = fibonacci(n-1);
            num1 = fibonacci(n);
        }

        printf("%d %d\n", num0, num1);
    }

    return 0;
}

 

처음에는 문제에 나와있는 대로 피보나치 수열을 재귀를 통해 구했는데, (당연히) 시간 초과라고 떴다. (오답) 그래서 어떻게 해야하나 막 검색해보기 시작했다. 어떤 사람은 그냥 40까지 쭉 계산을 해놓고 찾는 방식으로 코드를 짠 것 같았는데, 그렇게 짜는 건 좀 아닌 것 같아서 더 찾아봤더니 다이나믹 프로그래밍이라는 것이 있었다. 우리가 실제로 피보나치 수열을 구할 때처럼 앞에서부터 계산을 해서 더해나가는 건데, 이미 한 계산은 배열에 저장해두서 불필요한 계산 시간을 줄이는 방식이다. 이렇게 풀었더니 됐다! 시간복잡도가 선형으로 바뀐 것! (정답)