상상쓰

https://www.acmicpc.net/problem/1094 1094번: 막대기 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대 www.acmicpc.net 나는 몇 번의 과정을 거쳐서 64cm의 막대기가 Xcm가 됐는지를 구하는 줄 알았는데 막대기의 개수를 구하면 되는 문제였다. 이진수로 나타내어 1의 개수를 구하면 된다. import sys X = int(sys.stdin.readline()) answer = bin(X).count('1') print(answer)

https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net N = 5 로 예를 들면, N * N 배열은 아래와 같다. [1, 2, 3, 4, 5] [2, 4, 6, 8, 10] [3, 6, 9, 12, 15] [4, 8, 12, 16, 20] [5, 10, 15, 20, 25] 이분 탐색으로 나올 수 있는 수 중 최솟값인 1과 최댓값인 5*5(=25)를 시작으로 한 중간값(=mid)이 조건에 맞는지를 확인한다. 배열 안에 중..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 불금! import sys T = int(sys.stdin.readline()) dp = [[1, 0], [0, 1]] for i in range(39): dp.append([dp[-2][0] + dp[-1][0], dp[-2][1] + dp[-1][1]]) for i in range(T): N = int(sys.stdin.readline()) print(dp[N][0], end = ' ') print(dp[N][1])

https://www.acmicpc.net/problem/16500 16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 www.acmicpc.net A에 포함된 문자열을 한 개 이상 붙일 수 있으므로 dp[index] 가 1이면 이미 재귀함수로 A의 문자열로 S를 만들 수 있는지 확인하고 있으므로 무시해도 된다. DFS 알고리즘으로 S = 'softwarecontest' A = ['software', 'contest'] 라면 1) index = 0 (dp[0] = 1) : softwarecontest(= S[0:]) 와 ..

https://www.acmicpc.net/problem/23037 23037번: 5의 수난 키파는 문득 3과 4의 견고한 벽에 가로막혀 스포트라이트를 받지 못하는 5를 떠올렸다. '세상에 얼마나 많은 것들이 5와 관련이 있는데!' 키파는 5가 쓰이는 곳을 떠올리기 시작했다. 사람의 손가 www.acmicpc.net 오 신기방기 import sys n = sys.stdin.readline().strip() answer = sum(list(map(lambda x : int(x) ** 5, n))) print(answer)

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net dp[i] = i 를 마지막 원소로 가지는 증가하는 부분 수열의 길이 A[i] > A[j] (단, j = 0,1,2, ..., i-1) 일 경우 dp[j] + 1 중 가장 큰 값을 dp[i] 로 설정한다. dp 의 최댓값을 반환하면 된다. import sys N = int(sys.stdin.readline()) A = ..

https://www.acmicpc.net/problem/18185 18185번: 라면 사기 (Small) 라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i www.acmicpc.net i, i+1, i+2 공장에 라면이 있는 경우 7원으로 세 개의 라면을 사는 것이 가장 합리적이지만, [1, 2, 1, 1] 의 경우 7원으로 사는 것을 우선적으로 사버리면 [0, 1, 0, 1] 로 다음 번에 무조건 하나씩 사게 되어 최소한의 가격으로 사지 못하는 경우가 발생한다. [1, 2, 1, 1] 의 경우는 먼저 두 개의 공장에서 5원으로 라면을 산 뒤([0, 1, 1,..

https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 시간초과를 방지하기 위해서 크레인을 두 번째 이상 돌릴 때는 정렬된 박스들의 위치를 기억해서 무게 제한보다 무거운 박스인지는 비교하지 않도록 하였다. cranes = [9, 8, 6], boxes = [2, 2, 4, 5, 7] 이라고 가정했을 때, bisect_right 를 이용하여 positions = {9 : 5, 8 : 5, 6 : 4} 즉, 크레인 9번은 1 ~ 5번, 6..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net P[i] 를 i+1 장 뽑았을 때의 최댓값으로 값을 재설정한다. 예를 들어 카드가 5장 뽑았을 때의 최댓값은 카드를 1장 뽑았을 때의 최댓값 + 카드를 4장 뽑았을 때의 최댓값, 카드를 2장 뽑았을 때의 최댓값 + 카들르 3장 뽑았을 때의 최댓값, 카드를 5장 뽑았을 때의 값 중 최댓값이다. import sys N = int(sys.stdin.readline()) P = list(map(int, sys...

https://www.acmicpc.net/problem/1292 1292번: 쉽게 푸는 문제 첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다. www.acmicpc.net 군수열 문제로 수열 공식을 이용하여 답을 구할 수 있다. i 번째에 해당하는 숫자 찾기(계차수열, 근의 공식) x = (1 + math.sqrt(1 + 8 * (i - 1))) // 2 i 번째에 해당하는 숫자가 처음으로 등장하는 번호 찾기(계차수열) n = 1 + (x - 1) * x // 2 i 번째에 해당하는 숫자까지의 합(n - 1 번째까지의 합 + n 번째부터 i 번째까지의 합) n - 1 이 x 라면, 1^2..