조준장 개발자 생존기

문제 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 알고리즘 - 재귀와 백트래킹을 통해 문제를 수행한다. - 백트래킹 함수를 만들어 매개변수를 idx와 수열의 합으로 선언한다. - 현재 idx가 정수의 개수보다 크면 리턴한다. - 수열에 현재 idx 정수를 더한다. - 현재 수열의 합이 s라면 카운트한다. - 현재 idx 정수를 더한 값을 백트래킹 함수에 넣어 재귀적으로 탐색한다. - 위 탐색이 끝난 후 현재 idx 정수를 더하지 않은 값을 백트래킹으로 재귀적으로 다시 탐..

문제 1141번: 접두사 접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, www.acmicpc.net 알고리즘 - 다른 단어의 접두사가 되는 단어는 항상 다른 단어보다 크기가 작거나 같으므로 길이를 기준으로 정렬을 한다. - 반복문을 통해 현재 단어와 그 외 단어들을 확인한다. - 현재 단어보다 길이가 긴 단어들을 확인하고 현재 단어가 다른 단어의 접두사인지 확인한다. - 현재 단어가 접두사가 아니라면 res를 카운트한다. 코드 import sys n = int(sys.stdin.readline()..

문제 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 알고리즘 - 반복문을 통해 각 자리에 들어갈 사람을 확인한다. - 반복문을 통해 각 사람의 왼쪽에 키 큰 사람의 수를 확인한다. - 자신의 왼쪽에 키 큰 사람의 수가 카운트한 수와 맞고 그 자리에 아무도 없다면 그 자리는 그 사람의 자리다. - 자신의 왼쪽에 키 큰사람의 수가 카운트한 수가 아니고 자리에 아무도 없다면 자신의 왼쪽에 키 큰 사람의 수를 카운트한다. - 자신의 왼쪽에 키 큰 사람의 수가 카운트한 수가 아니고 자리에 있는 경우는 자신보다..

문제 1817번: 짐 챙기는 숌 첫째 줄에 책의 개수 N과 박스에 넣을 수 있는 최대 무게 M이 주어진다. N은 0보다 크거나 같고 50보다 작거나 같은 정수이고, M은 1,000보다 작거나 같은 자연수이다. N이 0보다 큰 경우 둘째 줄에 책 www.acmicpc.net 알고리즘 - 박스가 있는 경우와 없는 경우를 나눠 문제를 수행한다. - 박스가 있는 경우 반복문을 통해 책의 무게를 확인한다. - 박스에 넣을 수 있는 무게와 박스에 넣을 수 있는 최대 무게를 비교하여 박스에 넣을 수 있는 책의 개수를 카운트한다. - 책의 무게를 다 확인 후에도 박스에 넣어야 하는 책이 있는 경우에 박스를 하나 더 카운트한다. - 박스가 없는 경우는 0을 출력한다. 코드 import sys n, m = map(int,..

문제 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 알고리즘 - 1부터 n까지의 합의 공식을 이용하여 문제를 수행한다. - 반복문을 통해 합이 s보다 클 때의 n을 구하고 n - 1 값을 출력한다. 코드 import sys s = int(sys.stdin.readline()) n = 1 # n * (n + 1) / 2 => 1부터 n 까지의 합의 공식 # 반복문을 통해 합이 s보다 클 때의 n을 구한다. while n * (n + 1) / 2

문제 1531번: 투명 첫째 줄에 N과 M이 주어진다. N은 0보다 크거나 같고, 50보다 작거나 같다. M은 0보다 크거나 같고, 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 종이의 좌표가 주어진다. 왼쪽 아래 모서리의 x, y좌 www.acmicpc.net 알고리즘 - 일반 구현 문제로 문제를 이해하면 쉽게 풀 수 있다. - 반복문을 통해 불투명한 종이를 확인하여 불투명한 종이로 가려지는 그림에 카운트한다. - 반복문을 통해 모든 그림을 확인하여 m개 이상 불투명한 종이가 올라가 있는 그림을 카운트한다. - 카운트된 그림의 개수를 출력한다. 코드 import sys n, m = map(int, sys.stdin.readline().split()) drawing = [[0 for _ in range..

문제 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 알고리즘 - 반복문을 통해 연도를 계산한다. - 각 범위에 맞게 지구, 태양, 달의 수를 카운트하고 우리가 알고 있는 연도도 카운트한다. - 구해야 하는 지구, 태양, 달의 수라면 우리가 알고 있는 연도를 출력하고 반복을 멈춘다. 코드 import sys e, s, m = map(int, sys.stdin.readline().split()) curr_e = 0 # 현재 지구 curr_s = 0 # 현재 태양 curr_m = 0 # 현재 달 cnt = 0 # 우리..

문제 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 알고리즘 - 반복문을 통해 필요한 세트를 찾는다. - 반복문을 통해 필요한 숫자를 확인한다. - 필요한 숫자가 플라스틱 숫자 세트에 있으면 temp에 챙길 플라스틱 숫자를 추가하고 플라스틱 숫자 세트에선 제거한다. - 필요한 숫자가 플라스틱 숫자 세트에 없지만 6과 9인 경우의 위와 같이 수행한다. - 필요한 숫자를 챙기고 카운트한다. 코드 import sys n = list(map(int, sys.stdin.readline().strip())) cnt = 0 # 반복문을 통해 필요한 세트를 찾는다. while n: num = [0, 1, 2, 3, 4,..

문제 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 알고리즘 - 반복문을 통해 n번째 영화의 제목을 찾는다. - 현재 제목이 666을 포함되어 있다면 cnt를 카운트한다. - cnt가 구해야 하는 n번째 영화라면 six를 출력한다. - 매 사이클마다 제목을 카운트한다. 코드 n = int(input()) six = 666 cnt = 0 while True: # 현재 제목이 666을 포함되어있다면 cnt 카운트 if '666' in str(six): cnt += 1 # cnt가 구해야하는 n번째 영화라면 s..

문제 1312번: 소수 피제수(분자) A와 제수(분모) B가 있다. 두 수를 나누었을 때, 소숫점 아래 N번째 자리수를 구하려고 한다. 예를 들어, A=3, B=4, N=1이라면, A÷B=0.75 이므로 출력 값은 7이 된다. www.acmicpc.net 알고리즘 - 처음에 a를 b로 나눠 나머지를 a에 담는다. (1의 자릿수) - n - 1을 반복하여 나눗셈을 구현한다. (소수 n-1번째 자리까지 나눔) - 마지막 나눗셈의 몫을 출력한다. (n번째 자리 수를 나눈 몫을 출력) 코드 import sys a, b, n = map(int, sys.stdin.readline().split()) a %= b # 처음에 a를 b로 나눠준다. (1의 자리수) # n - 1 반복을 통해 나눗셈을 구현 for _ in..