본문 바로가기

수학23

[백준 2292] 벌집 (C++) https://www.acmicpc.net/problem/2292 문제위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다. 입력첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다. 출력입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다. 문제 풀이간단한 수학 문제. 1번은 처음이므로 하나의 방만 지나면 된다. 2.. 2024. 8. 27.
[백준 13909] 창문 닫기 (C++) https://www.acmicpc.net/problem/13909문제서강대학교 컴퓨터공학과 실습실 R912호에는 현재 N개의 창문이 있고 또 N명의 사람이 있다. 1번째 사람은 1의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다.  2번째 사람은 2의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 이러한 행동을 N번째 사람까지 진행한 후 열려 있는 창문의 개수를 구하라. 단, 처음에 모든 창문은 닫혀 있다.예를 들어 현재 3개의 창문이 있고 3명의 사람이 있을 때,1번째 사람은 1의 배수인 1,2,3번 창문을 연다. (1, 1, 1)2번째 사람은 2의 배수인 2번 창문을 닫는다. (1, 0, 1)3번째 사람은 3의 배수인 3번 창문을 닫는다. (1, 0, 0)결과적으로 마지막에 열려 있.. 2024. 8. 10.
[백준 2869] 달팽이는 올라가고 싶다 (C++) 문제땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오. 입력첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B  출력첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다. 문제 풀이수학 문제. 정상에 올라갈 때까지 반복문을 이용하면 시간 초과가 발생한다.달팽이가 정상에 올라갈 때까지 밤에 미끄러지다 마지막 하루는 낮에 모두 올라갈 수 있다. 다시 말해 나무 막대를 올라가는데 걸리는 날짜는 미끄러진 날짜의 일수 + .. 2024. 8. 9.
[백준 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.

티스토리툴바