[BOJ 5086] 배수와 약수 - 수학

문제 링크

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

문제 요약

두 수가 주어졌을 때, 첫 번째 수가 두 번째 수의 약수인지, 배수인지, 아니면 둘 다 아닌지 판별하는 문제

접근 방법

• 자료구조: 변수 2개
• 알고리즘: 나머지 연산을 이용한 약수/배수 판별
• 핵심 아이디어:
  • a가 b의 약수 → b % a == 0 (b가 a로 나누어떨어짐)
  • a가 b의 배수 → a % b == 0 (a가 b로 나누어떨어짐)
  • 0 0이 입력되면 종료

풀이 코드

#include <iostream>

int main() {
    int a, b;

    while(true) {
        std::cin >> a >> b;

        if(a == 0 && b == 0) {
            break;
        }

        if(b % a == 0) {
            std::cout << "factor" << std::endl;
        }
        else if(a % b == 0) {
            std::cout << "multiple" << std::endl;
        }
        else {
            std::cout << "neither" << std::endl;
        }
    }

    return 0;
}

시간/공간 복잡도

• 시간 복잡도: O(T) - T는 테스트 케이스 수
• 공간 복잡도: O(1)

실행 결과

• 메모리: 2020 KB
• 시간: 0 ms

참고한 풀이

• 나머지 연산(%)을 이용한 약수/배수 판별
• a가 b의 약수 ↔ b가 a의 배수 관계 이해