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

1/16. 공 (백준 1547번)

 

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

 

//C
#include <stdio.h>

int main()
{
    int ball = 1;
    int a, b, m;

    scanf("%d", &m);

    for(int i = 0; i < m; i++)
    {
        scanf("%d %d", &a, &b);

        if(a == ball)
            ball = b;
        else if(b == ball)
            ball = a;
    }

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

    return 0;
}

 

브론즈3인데 은근 애먹은 문제. 처음엔 생각없이 그대로 구현하려고 하다가 포인터까지 생각하게 되었고... 계속 머리를 싸매다가 이렇게 복잡한 문제는 아닌 것 같은데... 하면서 오빠한테 물어봤다. 오빠는 모든 걸 다 구현할 필요가 없다고, 필요한 정보만 구분해내서 필요한 것만 구현하면 된다고 했다. 처음에는 그 말을 이해를 못 했다. 알고 보면 좀 더 간단하게 생각하면 됐었다. 일단 ball이라는 변수 하나만 선언해놓고, 그 변수는 공이 어느 컵에 있는지를 나타내는 변수이다. 입력받은 두 수 중 공이 있는 위치가 있다면 그것이 아닌 다른 값을 ball에 저장하면 되고, 두 수 다 공이 있는 위치가 아니라면 아무것도 하지 않으면 된다. 즉, 공이 있는 위치만 저장해놓으면 된다는 말이다. (정답)

 

---

 

1/7. 별 찍기 - 3 (백준 2440번)

 

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

 

#python

n = int(input())

for i in range(n):
    print('*' * (n - i))

 

아직 파이썬과 친해지는 중... 사실 아직은 안면 트는 중..... (정답)

 

---

 

1/18. 세준세비 (백준 1524번)

 

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

 

#C
#include <stdio.h>
#include <stdlib.h>

int sj[1000000], sb[1000000];

int Compare(const void* _elem1, const void* _elem2)
{
	int* elem1 = (int*)_elem1;
	int* elem2 = (int*)_elem2;

	if (*elem1 > *elem2)
		return 1;
	else if (*elem1 < *elem2)
		return -1;
	else
		return 0;
}

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

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

        for(int j = 0; j < n; j++)
            scanf("%d", &sj[j]);
        for(int j = 0; j < m; j++)
            scanf("%d", &sb[j]);
        
        qsort((void*)sj, n, sizeof(int), Compare);
        qsort((void*)sb, m, sizeof(int), Compare);

        while(1)
        {
            if(sj[n-1] >= sb[m-1])
                m--;
            else
                n--;

            if((n == 0) || (m == 0))
                break;
        }

        if(n == 0)
            printf("B\n");
        else if(m == 0)
            printf("S\n");
        else
            printf("C\n");
    }

    return 0;
}

 

처음에는 삽입 정렬로 했는데 시간초과가 떴다. 그래서 C 내장 함수인 퀵정렬(qsort)을 사용했다. (qsort를 사용하려면 compare함수가 필요하다고 해서 따로 만들어줬다.) 퀵정렬로 다시 제출하니 맞았다. (정답)

(생각해보니 병사 세력의 최댓값이 큰쪽이 무조건 이긴다. 최댓값만 가지고 푸는 것도 해보자)

(그리고 n을 입력받고 int arr[n] 이런식으로 배열을 선언하는 것은 위험하다! 동적할당 malloc 찾아보고 배우자! 또는 전역변수로 넉넉히 선언해두자.)

 

---

 

1/19. 쉽게 푸는 문제 (백준 1292번)

 

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

 

//C
#include <stdio.h>

int sum(int n)
{
    int count = 0, sum = 0;

    if(n <= 0)
        return 0;
    
    for(int i = 1; i <= 1000; i++)
        for(int j = 0; j < i; j++)
        {
            sum += i;
            count ++;

            if(count >= n)
                return sum;
        }

}

int main()
{
    int start, end, ans;
    scanf("%d %d", &start, &end);

    ans = sum(end) - sum(start-1);
    printf("%d\n", ans);

    return 0;
}

 

시도했지만 맞지 못한 문제에서 고른 문제. 아마 스터디 2기에서 도전했던 문제 같은데 못 풀었던 것 같다. 내가 너무 어렵게 생각한거였다. 이번에도 엄청 복잡하게 풀다가 '아니 굳이 이렇게 돌아갈 필요가 없잖아..???' 하고 아예 처음부터 다시 짰다. 처음에는 몇번째 수가 무슨 수인지 구하고 그 사이의 수들을 다 더하려고 했는데, 어디서 잘못되었는지 계속 이상하게 출력되었다. (오답) 그런데 그냥 간단히 부분합으로 생각하고 풀면 쉬운 문제였다. a3+a4+a5가 s5-s2인 것처럼... 그래서 s에 해당하는 합을 구하는 함수를 따로 만들고 sum(end) - sum(start-1)로 답을 구했다. (정답)

 

---

 

1/20. DNA (백준 1969번)

 

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

 

//C
#include <stdio.h>

int main()
{
    int n, m;
    char dna[1000][52];
    char minDna[52];
    int minDis;

    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%s", &dna[i]);

    for (int i = 0; i < m; i++)
    {
        int num[4] = {0}; // 0:A 1:C 2:G 3:T
        
        for (int j = 0; j < n; j++)
        {
            if (dna[j][i] == 'A')
                num[0]++;
            else if (dna[j][i] == 'C')
                num[1]++;
            else if (dna[j][i] == 'G')
                num[2]++;
            else if (dna[j][i] == 'T')
                num[3]++;
        }

        int maxnum = 0, maxindex;

        for (int k = 0; k < 4; k++)
            if (num[k] > maxnum)
            {
                maxnum = num[k];
                maxindex = k;
            }
            
        if (maxindex == 0)
            minDna[i] = 'A';
        else if (maxindex == 1)
            minDna[i] = 'C';
        else if (maxindex == 2)
            minDna[i] = 'G';
        else if (maxindex == 3)
            minDna[i] = 'T';

        minDis += (n - maxnum);
    }

    printf("%s\n", minDna);
    printf("%d\n", minDis);

    return 0;
}

 

우리가 구해야 하는 dna를 minDna라고 하면, minDna의 첫번째 값은 반복문을 통해 파악했을 때 가장 많이 나온 알파벳이어야 한다는 점을 이용해서 풀었다. 실버5지만 어렵지 않게 성공! (정답)

 

---

 

1/21. 직사각형 네개의 합집합의 면적 구하기 (백준 2669번)

 

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

 

//C
#include <stdio.h>

int main()
{
    int square[100][100] = {0};
    int startx[4], starty[4], endx[4], endy[4];
    int area = 0;

    for (int i = 0; i < 4; i++)
    {
        scanf("%d %d %d %d", &startx[i], &starty[i], &endx[i], &endy[i]);
        
        for (int j = startx[i]; j < endx[i]; j++)
            for (int k = starty[i]; k < endy[i]; k++)
                square[j][k] = 1;
    }

    for (int i = 0; i < 100; i++)
        for (int j = 0; j < 100; j++)
            if (square[i][j] == 1)
                area++;

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

    return 0;
}

 

예전에 도전했다가 제출도 못 했던 문제였던 것 같다. 문제를 둘러보다가 익숙해보이길래 이걸 선택했다. 내 실력이 조금은 는걸까,,? (두근) 망설임 없이 바로 풀었다. 그냥 100*100인 이차원 배열을 선언하고 네개의 사각형을 검토하며 체크하기만 하면 끝! (정답) 그나저나 곧 실버로 승급할 수 있을 것 같다..!!!! 드디어!! 히히 빨리 문제 더 풀어야지!

 

---

 

1/22. 단어의 개수 (백준 1152번)

 

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

 

//C
#include <stdio.h>
#include <string.h>
#include <ctype.h>

int main()
{
    char str[1000002];
    int count = 0, flag = 1;
    fgets(str, sizeof(str), stdin);

    for (int i = 0; str[i] != '\0'; i++)
    {
        if (isalpha(str[i]))
        {
            if (flag == 1)
            {
                count++;
                flag = 0;
            }
        }
        else
            flag = 1;
    }

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

    return 0;
}

 

씨프실 수업에서 배운 기억이 있었던 예제! 두가지 방법이 있었다. 하나는 토큰 분리를 이용한 것이었고 하나는 플래그를 이용한 것이었다. 그런데 토큰 분리로 하려고 하니 문장 맨 끝에 공백이 나오는 경우 결과가 원하는 대로 출력되지 않아서 (그리고 그걸 어떻게 고쳐야 내가 원하는 대로 될지가 생각나지 않아서) 그냥 결국 플래그로 풀었다..!! (정답)