조준장 개발자 생존기

문제 1326번: 폴짝폴짝 첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음 줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 반복문을 통해 건너야 하는 다리를 모두 탐색한다. - 2개의 반복문을 통해 현재 다리에서 앞으로 가는 경우와 뒤로 가는 경우를 나눠 탐색한다. - 탐색 중 탐색하지 않은 다리가 나타나면 건너야 하는 다리 리스트에 추가하고 그 다리까지 점프한 수를 초기화한다. - 그때 탐색한 다리가 b번 다리라면 그때 탐색한 다리까지 점프한 수를 출력한다. - 모든 다리를 탐색한 후에도 b번 다리를 가지 못했..

문제 1283번: 단축키 지정 첫째 줄에 옵션의 개수 N(1 ≤ N ≤ 30)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄에 옵션을 나타내는 문자열이 입력되는데 하나의 옵션은 5개 이하의 단어로 표현되며, 각 단어 역시 10개 이하 www.acmicpc.net 알고리즘 - 반복문을 통해 모든 단어를 확인한다. - 1번과 2번의 방법을 한 번에 수행한다. - 반복문을 통해 단어의 첫 글자의 알파벳을 확인한다. - 현재 단어의 첫 글자가 단축기로 지정되어 있지 않다면 현재 단어의 첫 글자를 단축기로 지정하고 "[]"를 감싼 후 출력한다. - 다음으로 위 방법을 통해 break가 되지 않았다면 3번의 방법을 수행한다. - 위 방법과 다르게 단어의 첫 글자의 알파벳이 아닌 모든 단어의 알파벳을 순서대로 확..

문제 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,..