조준장 개발자 생존기

문제 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 알고리즘 - 반복문을 통해 모든 상자의 크기를 확인한다. - 다음 상자의 크기와 그전에 있는 모든 상자의 크기를 비교한다. - 마지막 상자의 크기가 다음 크기에 다음 상자의 크기보다 크다면 상자의 계수를 카운트한다. 코드 import sys n = int(sys.stdin.readline()) box = list(map(int, sys.stdin.readline().split())) # 상자안에 넣어진 상자의 계수 result = [1] * n for i in ra..

문제 1024번: 수열의 합 첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다. www.acmicpc.net 알고리즘 - 수열의 합 공식을 통해 식을 도출해낸다. n = x + (x+1) + (x+2) +... + (x+(l-1)) n = (x * l) + (1부터 l - 1까지 합) n = (x * l) + t x = (n - t) / l - 반복문을 통해 모든 길이를 확인한다. - 길이를 확인하면서 조건이 맞는지 확인 - 조건이 맞으면 그때 초기값과 길이를 가지고 반복하여 출력 코드 import sys n, l = map(int, sys.stdin.readline().split()) # 식 # n =..

문제 1660번: 캡틴 이다솜 캡틴 이다솜은 자신의 해적선에 적을 공격하기 위한 대포알을 많이 보관해 놓는다. 다솜이는 미적감각이 뛰어나기 때문에, 대포알은 반드시 사면체 모양으로 쌓아놓아야 한다고 생각한다. 사면 www.acmicpc.net 알고리즘 - 반복문을 통해 각 사면체를 만드는 데 사용되는 대포알의 개수를 list에 저장한다. - 반복문을 통해 대포알의 개수에 따라 만들 수 있는 사면체를 확인한다. - 현재 대포알의 개수로 만들 수 있는 사면체중 제일 작은 값을 dp에 저장한다. 코드 pypy3 해결 # pypy3 해결(python3 시간초과) import sys n = int(sys.stdin.readline()) balls = [] # 만들 수 있는 사면체 ball = 0 # 반복문을 통해..

문제 2502번: 떡 먹는 호랑이 첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤A≤B)가 존재한다. www.acmicpc.net 알고리즘 - 반복문을 통해 조건에 맞는 모든 경우를 탐색한다. - 할머니가 호랑이를 처음 만난 날에 준 떡의 개수 A, 그 다음 날에 호랑이에게 준 떡의 개수 B => 1≤A≤B이다. - d일까지 할머니가 떡을 주는 경우를 탐색하고 d 일어날 호랑이에게 준 떡이 k 개라면 A와 B를 출력하고 종료한다. 코드 import sys d, k = map(int, sys.stdin.readline().split()) # 반복문을 통해 조건에 맞는 모든 경우를 탐..

문제 2410번: 2의 멱수의 합 첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 알고리즘 - 2의 제곱일때마다 전체 dp에+이전 dp값을 더해준다. 코드 import sys n = int(sys.stdin.readline()) dp = [0] * (n + 1) dp[0] = 1 # 1 => 1, 1가지 # 2 => 2 11, 2가지 # 3 => 21 111, 2가지 # 4 => 4 22 211 1111, 4가지 # 5 => 41 221 2111 11111 4가지 two = [2 ** k for k in range(21)] # 2^k # 반복문을 통해 2의 멱수의 합을 구한다. for i in two: if i

문제 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 알고리즘 - 점화식을 구하면 쉽게 풀 수 있는 문제이다. - 좌석이 1개일 때 경우의 수는 1개이고 좌석이 2개일 때 경우의 수는 2개이고 좌석이 3개일 때 경우의 수는 3개이다. - 점화식: dp[n] = dp[n - 1] + dp[n - 2] - 각 좌석의 개수에 따라 경우의 수를 구했다면 vip 유무에 따라 경우의 수를 곱해주면 된다. - 반복문을 통해 vip 사이에 그룹에 들어가는 경우의 수를 확인해서 곱해줘 출력한다. - vip가 없다면 n좌석의 경우의 수를 ..

문제 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 알고리즘 - 반복문을 통해 코인으로 1부터 k까지의 가치를 만들 수 있는지 확인 - 현재 코인으로 현재 가치를 만들 수 있다면 이전에 현재 가치를 만든 코인의 개수와 i-j를 만든 코인의 개수에서 +1 해준 값을 비교하여 더 적게 코인을 사용한 개수로 초기화한다. - 반복문이 끝나고 k 가치를 구하기 위해 사용한 코인의 개수가 100001개라면 불가능한 경우인 것이고 아니라면 k 가치를 구하기 위해 사용한 코인의 개수를 출력한..

문제 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 알고리즘 - 암호를 해석할 수 있는지 없는지는 첫 번째 숫자가 0인지 아닌지에서 구별 가능하다. - 암호를 해석할 수 있다면 반복문을 통해 암호를 해석한다. - 암호는 2가지 경우로 해석할 수 있는지 확인한다. - 현재 탐색하고 있는 수가 해석 가능한지 확인, 현재 탐색하고 있는 수와 이전에 탐색한 수를 더한 수가 해석 가능한지 확인 - 2가지 경우를 탐색하고 마지막 수까지 해석 가능한 경우의 수를 출력한다. 코드 import sys word = list(map(int, s..

문제 1790번: 수 이어 쓰기 2 첫째 줄에 N(1 ≤ N ≤ 100,000,000)과, k(1 ≤ k ≤ 1,000,000,000)가 주어진다. N과 k 사이에는 공백이 하나 이상 있다. www.acmicpc.net 알고리즘 - 반복문을 통해 자릿수에 맞게 수를 빼준다. - 현재 수에는 자릿수에 맞게 뺀 수의 수를 더한다. - 자릿수를 이동하면서 1의 자리는 9개, 10의 자리는 18개.. 씩 개수를 빼준다. - 자릿수에 맞게 수를 빼줬다면 남은 자릿수의 수를 현재 수에 더해준다. - 현재 수가 n보다 크다면 -1을 출력하고 그게 아니라면 문자열로 변환 후 남은 자릿수의 값을 출력한다. 코드 import sys n, k = map(int, sys.stdin.readline().split()) ans ..

문제 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 알고리즘 - 시간 초과가 나오지 않게 하기 위해 재귀적으로 탐색한다. - 재귀적으로 탐색할 때 현재 수를 1번 곱해도 되는 거라면 현재 값을 c로 나눈 나머지를 리턴한다. - 곱해야 하는 수가 1보다 크다면 현재 수와 b//2로 나눈 값을 재귀적으로 탐색시킨다. - 탐색이 끝나고 나면 b가 짝수인지 홀수인지 확인한다. - 짝수라면 탐색이 끝난 후 리턴 받은 수를 2번 곱하고 c로 나눈 나머지 값을 리턴한다. - 홀수라면 탐색이 끝난 후 리턴 받은 수를 2번 곱하고 a를 한번 더 곱한 후 c로 나눈 나머지 값을 리턴한다. ..