[SISS/C언어 스터디] 25-1학기 5주차 스터디 - 완전 탐색, 추가 과제

[SISS/C언어 스터디] 25-1학기 5주차 스터디 - 완전 탐색, 추가 과제

: 5주차 (4/28~5/4) 프로그래머스 지정 1문제 (완전탐색)- https://school.programmers.co.kr/learn/courses/30/lessons/84512

 

모음 사전

---

// 모음 사전.c

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

// word가 사전에서 몇 번째 위치인지 반환
int solution(const char* word) {
    char vowels[] = {'A', 'E', 'I', 'O', 'U'};  // 사용 가능한 모음
    int weights[] = {781, 156, 31, 6, 1};       // 각 자리수의 가중치 (5^n - 1의 합 기반)

    int answer = 0;

    // 단어의 각 글자 순회
    for (int i = 0; word[i] != '\0'; i++) {
        // 현재 글자의 모음 배열 순서
        for (int j = 0; j < 5; j++) {
            if (word[i] == vowels[j]) {
                // 이전 문자들에 의해 가능한 모든 단어 수 + 현재 문자 포함 (+1)
                answer += j * weights[i] + 1;
                break;  // 찾은 경우
            }
        }
    }

    return answer;  // 순서 반환
}

모음 사전

 

13305

---

• 그리디 알고리즘

→ https://www.acmicpc.net/problem/13305

// 13305.c

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

int main() {
    int n;
    scanf("%d", &n);  // 도시 개수 입력

    // n-1개의 도시 사이 거리 배열
    int* distance = (int*)malloc((n - 1) * sizeof(int));

    // 각 도시의 리터당 기름값 배열
    int* costs = (int*)malloc(n * sizeof(int));

    // 거리 입력
    for (int i = 0; i < n - 1; i++) {
        scanf("%d", &distance[i]);
    }

    // 주유 비용 입력
    for (int i = 0; i < n; i++) {
        scanf("%d", &costs[i]);
    }

    long long total = 0;        // 총 이동 비용
    int minCost = costs[0];     // 현재까지 발견된 최소 주유 가격

    // 거리만큼 반복 (도시 수 - 1)
    for (int i = 0; i < n - 1; i++) {
        // 현재 도시의 주유 가격이 더 싸면 갱신
        if (costs[i] < minCost) {
            minCost = costs[i];
        }

        // 최소 주유 가격으로 비용 누적
        total += (long long)minCost * distance[i];
    }

    // 총 비용
    printf("%lld\n", total);

    // 메모리 해제
    free(distance);
    free(costs);

    return 0;
}

13305