본문 바로가기
반응형

알고리즘 테스트58

백준 2869 - 달팽이는 올라가고 싶다(파이썬) https://www.acmicpc.net/problem/2869 문제 풀이 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) www.acmicpc.net 문제 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다. 달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) 출력 첫째.. 2022. 1. 23.
백준 1193 - 분수찾기(파이썬) https://www.acmicpc.net/problem/1193 문제 풀이 1193번: 분수찾기첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.www.acmicpc.net풀이 코드n= int(input())index = int((1+((8*n-7)**.5))*.5)mole= int(n - (index-1)*(index)*.5)deno = index - mole +1print(f"{mole}/{deno}" if index %2 ==0 else f"{deno}/{mole}")코드 해설먼저 문제 속에 숨어있는 수학적 규칙을 찾아서 풀이했다!!이해하기 쉽게 배열을 사선으로 나누어 생각해보면 배열index분수전체 인덱스기준 범위11/1121/2, 2/12~333/1, 2/2, 1/34~641/4, .. 2022. 1. 23.
백준 2292 - 벌집(파이썬) https://www.acmicpc.net/problem/2292 해당 문제풀이입니다. 2292번: 벌집위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌www.acmicpc.net 코드 import mathan = int(input())#n테두리의 끝방번호는 계차수열 an= 1+3(n(n-1)) // {bn = 6n}#일반항 3n^2 - 3n + 1-an = 0#근의공식중 양수#그사이에 해당하는 방은 전부 올림처리 answer = math.ceil((3+(12*an -3)**(1/2))/6)print(answer)   풀이문제를 보니  1, 7, 19, 37, 61.. 2022. 1. 22.
에라토스테네스의 체(소수 판별 알고리즘) 유명한 소수 개수 찾기 알고리즘 다수의 소수를 찾을때 사용하는 알고리즘으로 하나의 숫자마다 소수인지 판별하는 것보다 효율적이라 많이 사용한다! 소수의 배수는 소수일수가 없다는 점을 이용한 알고리즘으로 2부터 숫자를 높여가며 자기 자신을 제외한 배수를 전부 지우는 방법이다. 방법 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색) 자기 자신을 제외한 3의 배수를 모두 지운다. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색) 자기 자신을 제외한 5의 배수를 모두 지운다.. 2021. 12. 28.
반응형

티스토리툴바