본문 바로가기
반응형

공부/백준\BeakJoon

 (24)
[BEAKJOON] 백준 1463번 : 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 설명 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. DP- BottomUp (for 문 사용) 문제 해결 방법 처음에 dp라는 리스트를 num+1만큼의 크기만큼 0으로 초기화해준다. dp[1]=0, 그러면 dp[1]은, 값이 1일 경우, 1이 되는 경우의 수는..
[BEAKJOON] 백준 9613번 : GCD 합, 파이썬 Python https://www.acmicpc.net/problem/9613 9613번: GCD 합 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 0): a, b = b, a%b return a num = int(input()) while(num): num -= 1 list_num = list(map(int, input().split())) count = 0 for i in range(1, list_num[0]..
[BEAKJOON] 백준 17298번 : 오큰수 - 파이썬 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다. 예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다..
[BEAKJOON] 백준 1212번 : 8진수 2진수 https://www.acmicpc.net/problem/1212 1212번: 8진수 2진수 첫째 줄에 8진수가 주어진다. 주어지는 수의 길이는 333,334을 넘지 않는다. www.acmicpc.net 문제 단순히 숫자 하나를 2진수에 맞게 치환해주면 되는 것 같아서 그렇게 코드를 작성했다. num = str(input()) result = '' for i in range(len(num)): if(num[i]=='0'): result += '000' elif(num[i]=='1'): result += '001' elif(num[i]=='2'): result += '010' elif(num[i]=='3'): result += '011' elif(num[i]=='4'): result += '100' eli..
[백준/BEAKJOON] 2089번 -2진수 https://www.acmicpc.net/problem/2089 2089번: -2진수 -2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 20, 21, 22, 23이 표현 되지만 -2진법에서는 (-2)0 = 1, (-2)1 = -2, (-2)2 = 4, (-2)3 = -8을 표현한다. 10진수로 1부터 표현하자면 1, 110, 111, 100, 101, 11010, 110 www.acmicpc.net 문제 -2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 20, 21, 22, 23이 표현 되지만 -2진법에서는 (-2)0 = 1, (-2)1 = -2, (-2)2 = 4, (-2)3 = -8을 표현한다. 10진수로 1부터 표현하자면 1, 110, 111, 100, 101, 11010, 1101..
[백준/BEAKJOON] 17103번 골드바흐 파티션 https://www.acmicpc.net/problem/17103 17103번: 골드바흐 파티션 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. www.acmicpc.net 문제 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다. 짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다. https://na0-0.tistory.com/107 위의 문제와 유사하게 해결할 수 있다. 100만 이하의 수에 대해, 에라토스테네스의 체로 ..
[BEAKJOON] 백준 1676번 : 팩토리얼 0의 개수 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 0과 500사이의 수 N을 입력받아, N!의 뒤에서부터 처음으로 0이 아닌 다른 수가 나올때까지 0의 개수를 출력하는 알고리즘을 구현하는 것이 목표이다. 문제풀이 N!의 뒤에서부터 처음으로 0이 아닌 다른 수가 나올때까지 0의 개수를 출력하는 문제이다. 예를 들어, 10!은 3628800이므로, 0의 개수가 2개, 3!은 6이므로, 0의 개수가 0개가 된다. 문제에서 구하고자하는 바는 10(2x5)의 개수를 구하면 된다. 예를 들어, 10! 같은 경우에는 , 10 (2 x 5)..
[BEAKJOON] 백준 2004번 : 조합 0의 개수 https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 문제 접근 이전 팩토리얼 문제를 풀어봤으면, 한 팩토리얼 값의 5의 승수가 겹치는 수를 구해야한다. 문제는 nCr의 값을 구하는 것이기 때문에, 이항 계수의 공식을 생각하면 된다. 이항 계수의 공식은 팩토리얼 값으로 이루어져 있어서 이를 이용하면 쉽게 풀 수 있을 것이다. 조합은 영어로 combination이며, 고교 수학 내에서는 대문자 C를 사용하여 표현한다. 조합의 뜻은, nCr 의 뜻은 'n개 중에서 순서에 상관없이 r개를 뽑는 경우의 수' 이다. ..
반응형

티스토리툴바