[Baekjoon] 단계별로 풀어보기 : 일반 수학 1

자료구조와 알고리즘/문제풀이

[Baekjoon] 단계별로 풀어보기 : 일반 수학 1

순정법사 2023.08.25

이번 알고리즘 문제 풀이는 C로 진행했습니다

코드에 오탈자나 문제가 있으면 언제든지 댓글로 알려주세요!

A. 일반 수학 1

일반 수학 1 단계

벌집이 형성되는 규칙에 따라 벌집의 위치를 구하는 문제

www.acmicpc.net

1. 진법 변환

a. 문제지 : 2745

b. 알고리즘 / 풀이

입력 받을 문자열 N과 변환할 진법 B를 선언하고 입력받음
문자를 숫자로 변환하는 함수 getNumber를 정의
a) 주어진 문자가 '0'부터 '9' 사이인 경우 해당 숫자로 변환
b) 'A'부터 'Z' 사이인 경우 10부터 35까지의 숫자로 변환하여 반환
입력된 문자열 N의 길이를 계산
결과를 저장할 변수 result를 초기화
입력된 문자열의 각 자릿수에 대해 반복문을 실행
a) getNumber(N[length - 1 - i])를 통해 현재 자릿수의 문자를 숫자로 변환하여 num에 저장
b) pow(B, i)를 통해 현재 자릿수에 해당하는 진법의 가중치를 계산
c) num과 가중치를 곱한 값을 result에 더함
변환된 결과 result를 출력

c. 정답

📚 풀이

#include <stdio.h>
#include <string.h>
#include <math.h>

// 문자를 숫자로 변환하는 함수
int getNumber(char c) {
    if ('0' <= c && c <= '9') {
        return c - '0'; // 문자 '0' ~ '9'를 숫자 0 ~ 9로 변환
    } else {
        return c - 'A' + 10; // 문자 'A' ~ 'Z'를 숫자 10 ~ 35로 변환
    }
}

int main() {
    char N[100]; // 입력 받을 문자열을 저장할 배열
    int B; // 진법을 나타낼 변수
    scanf("%s %d", N, &B); // 문자열 N과 진법 B 입력 받기

    int length = strlen(N); // 입력된 문자열의 길이 계산
    int result = 0; // 결과를 저장할 변수 초기화

    // 입력된 문자열의 각 자릿수에 대해 반복
    for (int i = 0; i < length; i++) {
        int num = getNumber(N[length - 1 - i]); // 오른쪽부터 숫자 변환
        result += num * (int)pow(B, i); // 가중치를 곱하여 결과에 더하기
    }

    printf("%d\n", result); // 변환된 결과 출력

    return 0;
}

2. 진법 변환 2

a. 문제지 : 11005

b. 알고리즘 / 풀이

입력 받은 10진법 수 N과 변환할 진법 B 받기
변환 결과를 저장할 문자열을 생성
N이 0이 될 때까지 다음 과정을 반복
a) N을 B로 나눈 나머지를 구하기 (현재 자릿수에 해당하는 숫자)
b) 나머지 값을 문자로 변환하여 결과 문자열에 추가
c) N을 B로 나누어 다음 자릿수를 계산
결과 문자열을 역순으로 출력

c. 정답

📚 풀이

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

// 10진법 수를 B진법으로 변환하는 함수
char toChar(int num) {
    if (num < 10) {
        return num + '0'; // 0~9의 경우 숫자 문자로 변환 (숫자 0)
    } else {
        return num - 10 + 'A'; // 10 이상의 경우 알파벳 문자로 변환
    }
}

int main() {
    int N, B;
    scanf("%d %d", &N, &B); // 10진법 수 N과 변환할 B진법 입력 받기

    char result[100]; // 변환 결과를 저장할 배열
    int idx = 0; // 배열의 인덱스 변수

    // N이 0보다 클 때까지 반복
    while (N > 0) {
        int remainder = N % B; // 나머지 계산
        result[idx++] = toChar(remainder); // 변환하여 결과 배열에 추가
        N /= B; // N을 B로 나누어 다음 자릿수 계산
    }

    // 배열에 저장된 결과를 역순으로 출력
    for (int i = idx - 1; i >= 0; i--) {
        printf("%c", result[i]); // 변환된 B진법 수 출력
    }

    printf("\n"); // 줄바꿈

    return 0;
}

3. 세탁소 사장 동혁

a. 문제지 : 2720

b. 알고리즘 / 풀이

테스트 케이스 개수 T를 선언하고 받음
T만큼 반복해서 거스름값을 받음
각 거스름값을 쿼터 / 다임 / 니켈 / 페니 순으로 나눠 각각의 값을 저장
각 값을 공백을 사용해 출력함

두개의 풀이방식에 차이점은 그저 가독성뿐..! 첫번째 방식이 코드 길이가 조금 더 짧긴 하다

c. 정답

📚 풀이 : 각 값을 변수화해 반복문으로 풀이

#include <stdio.h>

int main(){
    int T;
    scanf("%d", &T);
    
    for(int i=0; i<T; i++){
        int money;
        scanf("%d", &money);
        
        int mount[4] = {25, 10, 5, 1};
        int charge[4] = {0};
        
        for(int j=0; j<4; j++){
            if(money/mount[j]>=1){
                charge[j] = money/mount[j];
                money %= mount[j];
            }
        }
        printf("%d %d %d %d\n", charge[0], charge[1], charge[2], charge[3]);
    }
    return 0;
}

📚 풀이 : 가독성 업!!

#include <stdio.h>

int main() {
    int T;
    scanf("%d", &T); // 테스트 케이스 개수 입력

    for (int t = 0; t < T; t++) {
        int C;
        scanf("%d", &C); // 거스름돈 입력

        int quarter, dime, nickel, penny; // 필요한 동전 개수 변수 선언

        quarter = C / 25; // 쿼터의 개수 계산
        C %= 25; // 쿼터를 제외한 나머지 거스름돈 계산

        dime = C / 10; // 다임의 개수 계산
        C %= 10; // 다임을 제외한 나머지 거스름돈 계산

        nickel = C / 5; // 니켈의 개수 계산
        penny = C % 5; // 페니의 개수 계산

        printf("%d %d %d %d\n", quarter, dime, nickel, penny); // 결과 출력
    }

    return 0;
}

문제에 있던 영상... 그냥 노래가 좋아서 넣어둔듯 하다 ㅎ.ㅎ

4. 중앙 이동 알고리즘

a. 문제지 : 2903

b. 알고리즘 / 풀이

면적을 구한다고 생각하면 쉽다

첫 번째 사각형의 가로의 점 2개 ➡ 면적 4

두 번째 사각형의 가로의 점 3개 ➡ 면적 9

세 번째 사각형의 가로의 점 5개 ➡ 면적 25

가로의 점은 점과 점 사이에 추가되기 때문에 현재 점 -1만큼 추가현재 가로의 점이 cnt라면 다음 가로의 점은 2*cnt -1

초기 가로의 점은 2개니까 cnt = 2이고while이 0이 될때 멈추는 성질을 이용해 반복해 cnt+= cnt-1로 가로의 점을 구한다음cnt의 제곱을 하면 됨

c. 정답

📚 풀이

#include <cstdio>

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

	int cnt = 2;
	while (n--) {
    	cnt += (cnt - 1);
    }

	printf("%d\n", cnt * cnt);
	return 0;
}

[백준 BOJ] 2903 중앙 이동 알고리즘

2903_중앙 이동 알고리즘 링크 https://www.acmicpc.net/problem/2903 풀이 너무 깊게 생각하지 말고 점이 일정한 간격을 두고 채워져 있기 때문에 점을 이용해서 면적을 구한다고 생각해봅시다. 사각형들은

jaemin8852.tistory.com

5. 벌집

a. 문제지 : 2292

b. 알고리즘 / 풀이

위와 같은 이미지로 벌집이 반복되므로 코드를 작성하면 된다!

c. 정답

📚 풀이

#include <stdio.h>

int main(){
    int N;    //입력 받는 숫자값
    scanf("%d", &N);
    
    int pass = 1;    //지나간 방의 개수
    int maxRoom = 1;    //지나간 방의 최대 숫자
    
    while(N-maxRoom>0){    //입력받은 값이 최대 방 숫자보다 작을때까지 방 갯수 증가
        maxRoom += 6*pass;
        pass++;
    }
    
    printf("%d", pass);   
    return 0;
}

6. 분수 찾기

a. 문제지 : 1193

b. 알고리즘 / 풀이

거의 다 맞췄는데 문제를 잘못 읽어서 틀렸었다 ㅠ.ㅠ

c. 정답

📚 풀이

#include <stdio.h>

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

    int line = 1; // 현재 대각선 라인
    while (X > line) {
        X -= line; // 대각선 라인 순서에서 빼줌
        line++;
    }

    // 짝수 라인일 경우 분자는 X, 분모는 line - X + 1
    // 홀수 라인일 경우 분자는 line - X + 1, 분모는 X
    if (line % 2 == 0) {
        printf("%d/%d\n", X, line - X + 1);
    } else {
        printf("%d/%d\n", line - X + 1, X);
    }

    return 0;
}

7. 달팽이는 올라가고 싶다

a. 문제지 : 2869

b. 알고리즘 / 풀이

👉 문제 풀이시간 떄문에 반복문은 사용하면 안됨 (0.25초)

1) 개미의 이동날짜를 미리 계산해서 풀이

(V - B - 1) : 목표 지점 V 에서 미끄러지는 거리 B 를 뺀 값
개미가 미끄러지는 일 없이 도달해야 할 실제 거리
-1 은 개미가 마지막에 미끄러지는 경우를 고려하여 1을 빼준 것
(A - B) : 개미가 한 번의 이동에서 오르는 거리
(V - B - 1) / (A - B) : 개미가 목표 지점에 도달하기 위해 필요한 최소한의 이동 횟수
+ 1 : 개미가 처음에 한 번의 이동을 추가

2) 조건 그대로 수식을 만들어서 풀이

정상에 도달하면 미끄러지는 것은 고려 X
따라서 (A-B)×(days-1)+A ≥ V 조건을 만족하는 days의 최솟값을 구하는 수식을 생성
수식을 정리해 days >= (V-A)/(A-B) + 1로 변경해줌
days는 날짜라서 정수여야 하고, (V-A)/(A-B)값의 나머지값이 있는지 확인해야 함
정수임을 확인하는 방법으로 나머지 값이 0인지 확인하는 방법을 사용하는데
a) 정수라면 days = (V-A)/(A-B) + 1로 계산 (원래 하루부터 시작)
b) 아니면 n = (V-A)/(A-B) + 2로 계산 (하루를 더해야 하니까)
days 출력

C. 정답

📚 풀이 : 개미의 이동날짜를 미리 계산해서 풀이

#include <stdio.h>

int main(){
    int A, B, V;
    scanf("%d %d %d", &A, &B, &V);
    
    int days = (V - B - 1) / (A - B) + 1;
    
    printf("%d", days);
    return 0;
}

📚 풀이 : 조건 그대로 수식을 만들어서 풀이

#include <stdio.h>
 
int main(void){
    int A, B, V;
    scanf("%d %d %d", &A, &B, &V);
 
    int n;
    if((V-A)%(A-B)==0){
        n = (V-A)/(A-B)+1;
    }
    else{
        n = (V-A)/(A-B)+2;
    }
    printf("%d\n", n);
}

'자료구조와 알고리즘 > 문제풀이' 카테고리의 다른 글

[Baekjoon] 단계별로 풀어보기 : 기하 직사각형과 삼각형 (0)	2023.08.25
[Baekjoon] 단계별로 풀어보기 : 약수, 배수와 소수 (0)	2023.08.25
[Baekjoon] 단계별로 풀어보기 : 2차원 배열 (0)	2023.08.25
[Baekjoon] 단계별로 풀어보기 : 심화 1 (0)	2023.08.24
[Baekjoon] 단계별로 풀어보기 : 문자열 (0)	2023.08.17

현재글[Baekjoon] 단계별로 풀어보기 : 일반 수학 1

게임 개발 스킬트리