본문 바로가기

수학29

[백준 15829] Hashing (C++) 문제APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정의한다. 해시 함수는 무궁무진한 응용 분야를 갖는데, 대표적으로 자료의 저장과 탐색에 쓰인다.이 문제에서는 여러분이 앞으로 유용하게 쓸 수 있는 해시 함수를 하나 가르쳐주고자 한다. 먼저, 편의상 입력으로 들어오는 문자열에는 영문 소문자(a, b, ..., z)로만 구성되어있다고 가정하자. 영어에는 총 26개의 알파벳이 존재하므로 a에는 1, b에는 2, c에는 3, ..., z에는 26으로 고유한 번호를 부여할 수 있다. 결과적으로 우리는 하나의 문자열을 수열로 변환할 수 있다. 예를 들어서 문자열 "abba"은 .. 2024. 8. 7.
[백준 2577] 숫자의 개수 (C++) https://www.acmicpc.net/source/81591784 문제세 개의 자연수 A, B, C가 주어질 때 A × B × C를 계산한 결과에 0부터 9까지 각각의 숫자가 몇 번씩 쓰였는지를 구하는 프로그램을 작성하시오.예를 들어 A = 150, B = 266, C = 427 이라면 A × B × C = 150 × 266 × 427 = 17037300 이 되고, 계산한 결과 17037300 에는 0이 3번, 1이 1번, 3이 2번, 7이 2번 쓰였다. 입력첫째 줄에 A, 둘째 줄에 B, 셋째 줄에 C가 주어진다. A, B, C는 모두 100보다 크거나 같고, 1,000보다 작은 자연수이다. 출력첫째 줄에는 A × B × C의 결과에 0 이 몇 번 쓰였는지 출력한다. 마찬가지로 둘째 줄부터 열 번.. 2024. 7. 25.
[백준 29717] 슬라임 잡고 레벨 업! (C++) https://www.acmicpc.net/problem/29717문제오늘은 많은 사람이 기대하던 《실브 스토리》게임이 출시되는 날이다!《실브 스토리》는 MMORPG 장르 게임으로, 몬스터를 잡아 경험치를 모으고 레벨 업을 할 수 있으며, 레벨 업에 필요한 경험치를 넘을 때마다 그에 필요한 경험치만 소진하고 남은 경험치를 그대로 보유한다. 하지만 일반 게임들과 다르게 특이한 점이 두 가지 있다.첫 번째는 게임에 존재하는 몬스터가 슬라임뿐이라는 것이다. 슬라임을 처치했을 때 주는 경험치 또한 특이한데, 유저가 지금까지 처치한 슬라임 수를 𝑥라 할 때, 새로운 슬라임을 처치하면 𝑥+1 만큼의 경험치를 얻게 된다.두 번째는 레벨 업에 필요한 경험치의 증가 방식이다. 현재 레벨에서 레벨 업에 필요한 경험치가.. 2024. 7. 21.
[백준 30802] 웰컴 키트 (C++) https://www.acmicpc.net/problem/30802문제2024년 2월 3일 개최 예정인 온사이트 그랜드 아레나에서는 참가자들에게 티셔츠 한 장과 펜 한 자루가 포함된 웰컴 키트를 나눠줄 예정입니다. 키트를 제작하는 업체는 다음과 같은 조건으로만 주문이 가능합니다.티셔츠는 S, M, L, XL, XXL, 그리고 XXXL의 6가지 사이즈가 있습니다. 티셔츠는 같은 사이즈의 𝑇장 묶음으로만 주문할 수 있습니다.펜은 한 종류로, 𝑃자루씩 묶음으로 주문하거나 한 자루씩 주문할 수 있습니다.총 𝑁명의 참가자 중 S, M, L, XL, XXL, XXXL 사이즈의 티셔츠를 신청한 사람은 각각 𝑆, 𝑀, 𝐿, 𝑋𝐿, 𝑋𝑋𝐿, 𝑋𝑋𝑋𝐿명입니다. 티셔츠는 남아도 되지만 부족해서는 .. 2024. 7. 18.
[백준 1456] 거의 소수 (C++) https://www.acmicpc.net/problem/1456문제어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다.두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. 입력첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다. 출력첫째 줄에 총 몇 개가 있는지 출력한다. 제한1 ≤ A ≤ B ≤ 1014 문제 풀이에라토스테네스의 체를 활용한 문제. sqrt(B)를 초과하는 수에 대해서는 2제곱의 값이 B를 넘어가므로 거의 소수가 존재하지 않는다. 따라서 sqrt(B)까지의 소수들을 에라토스테네스의 체를 이용해 구해 벡터에 저장한다.모든 소수들을 구했다면 벡터의 각 원소(=소수)들에 대해 A와 B .. 2024. 7. 14.
[백준 14241] 슬라임 합치기 (C++) https://www.acmicpc.net/problem/14241문제영선이와 효빈이는 슬라임을 합치는 게임을 하고 있다. 두 사람은 두 슬라임을 골라서 하나로 합쳐야 한다. 게임은 슬라임이 하나 남았을 때 끝난다.모든 슬라임은 양수 크기를 가지고 있다. 두 슬라임 x와 y를 합쳤을 때, 합친 슬라임의 크기는 x+y가 된다. 또한, 슬라임을 합칠 때 마다 두 사람은 x*y 점수를 얻게 된다.영선이와 효빈이가 얻을 수 있는 점수의 최댓값을 구하는 프로그램을 작성하시오. 입력첫째 줄에 슬라임의 개수 N (2 ≤ N ≤ 100)이 주어진다.둘째 줄에는 슬라임의 크기가 주어진다. 크기는 100보다 작거나 같은 자연수이다. 출력첫째 줄에 영선이와 효빈이가 얻을 수 있는 점수의 최댓값을 출력한다. 문제 풀이그리디 .. 2024. 6. 25.
[백준 2485] 가로수 (C++) https://www.acmicpc.net/problem/2485문제직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다.편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다.예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다.심어져 있는 가로수의 위치가 주어질 때,.. 2024. 6. 15.
[백준 2436] 공약수 (C++) https://www.acmicpc.net/problem/2436 문제어떤 두 자연수에 공통인 약수들 중에서 가장 큰 수를 최대공약수라고 하고, 두 자연수의 공통인 배수들 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 두 자연수 12와 90의 최대공약수는 6이며, 최소공배수는 180이다.이와 반대로 두 개의 자연수 A, B가 주어졌을 때, A를 최대공약수로, B를 최소공배수로 하는 두 개의 자연수를 구할 수 있다. 그러나, 이러한 두 개의 자연수 쌍은 여러 개 있을 수 있으며, 또한 없을 수도 있다. 예를 들어, 최대공약수가 6이며 최소공배수가 180인 두 정수는 위의 예에서와 같이 12와 90일 수도 있으며, 30과 36, 18과 60, 혹은 6과 180일 수도 있다. 그러나, 최대공약수가 .. 2024. 6. 3.
[백준 27724] 팝핀 소다 (C++) https://www.acmicpc.net/problem/27724문제민겸이는 shake! 2022를 맞아 레크리에이션 행사를 기획하였다. 이 행사의 메인 컨텐츠는 탄산이 매우 강력해서 마시기 힘든 팝핀 소다를 빨리 마시는 대회이다. 이 대회는 아래와 같이 진행된다.대회에는 총 𝑁(단, 𝑁은 2의 거듭제곱수)명의 선수가 참가한다. 𝑁명의 선수들은 양의 정수로 표현 가능한 탄산 내성을 가지고 있다. 각 선수의 탄산 내성은 1 이상 𝑁 이하이며, 각 선수의 탄산 내성은 중복되지 않는다. 𝑁명의 선수들은 다른 선수와 두 명씩 짝지어 빨리 마시기 대결을 한다. 이 과정에서 총 𝑁/2번의 대결이 진행된다. 각 대결의 패자 𝑁/2명은 대회에서 나가고, 승자 𝑁/2명은 동일한 방식으로 두 명씩 짝지어 .. 2024. 5. 25.