[SISS/C언어 스터디] 2학기 3주차 스터디

2학기 3주차 스터디

백준 제출 내역 화면 캡쳐

자율 2문제를 풀어서 제출하면 됩니다.

언어는 C언어만 가능합니다.

​레벨 제한사항: Silver 5 이상

 

1541

---

• 그리디 알고리즘 → 값이 최소가 되는 방법 찾기

// 1541.c

#include <stdio.h>
#include <stdlib.h> // atoi 사용
#include <ctype.h>  // isdigit 사용
#include <string.h> // memmove 사용

int main()
{
    char ipt[100];               // 입력
    int numbers[50];             // 숫자 저장 배열
    char signs[50];              // 부호 저장 배열
    int minus = 0;               // 마이너스 여부
    int sum = 0;                 // 합계
    int numCnt = 0, signCnt = 0; // 숫자와 부호 개수 카운트
    int i = 0;                   // 인덱스 변수

    // 입력
    scanf("%s", ipt);

    // 숫자와 부호 나누기
    // 문자열의 끝('\0')이 아닐 때
    while (ipt[i] != '\0')
    {
        // 숫자가 아닐 경우 (연산자일 경우)
        if (!isdigit(ipt[i]))
        {
            numbers[numCnt++] = atoi(ipt);              // 숫자를 배열에 추가 (부호 전까지 숫자로 변환)
            signs[signCnt++] = ipt[i];                  // 부호를 배열에 추가
            memmove(ipt, ipt + i + 1, strlen(ipt) - i); // 남은 문자열로 ipt 업데이트
            i = 0;                                      // 인덱스 초기화
        }
        else
        {
            i++;
        }
    }
    // 마지막 숫자 추가
    numbers[numCnt++] = atoi(ipt);

    // 계산 과정
    for (i = 0; i < numCnt; i++)
    {
        if (i == 0)
        {
            sum += numbers[0]; // 첫 번째 숫자는 바로 더함
        }
        else
        {
            // 이전 부호가 '+'일 경우
            if (minus = 0)
            {
                if (signs[i - 1] == '+')
                {
                    sum += numbers[i];
                }
                else if (signs[i - 1] == '-')
                {
                    sum -= numbers[i];
                    minus = 1;
                }
            }
            // 이전 부호가 '-'일 경우
            else
            {
                if (signs[i - 1] == '+')
                {
                    sum -= numbers[i];
                }
                else if (signs[i - 1] == '-')
                {
                    sum += numbers[i];
                }
            }
        }
    }

    // 결과 출력
    printf("%d\n", sum);

    return 0;
}

 

1931

---

• 그리디 알고리즘 → 먼저 끝나는 것을 선택

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

// 먼저 두 번째 값을 기준으로 정렬하고, 값이 같으면 첫 번째 값으로 정렬
int compare(const void *a, const void *b) {
    int *pairA = (int *)a;
    int *pairB = (int *)b;
    
    if (pairA[1] == pairB[1]) {
        return pairA[0] - pairB[0];
    }
    return pairA[1] - pairB[1];
}

int main() {
    int n;
    int time = 0, team = 0;
    
    // 입력
    scanf("%d", &n);
    
    // 2차원 배열로 시작 시간과 끝 시간 저장
    int d[n][2];
    
    for (int k = 0; k < n; k++) {
        scanf("%d %d", &d[k][0], &d[k][1]);
    }
    
    // 정렬
    qsort(d, n, sizeof(d[0]), compare);
    
    for (int k = 0; k < n; k++) {
        if (time <= d[k][0]) {
            time = d[k][1];
            team++;
        }
    }
    
    // 결과 출력
    printf("%d\n", team);
    
    return 0;
}