조준장 개발자 생존기

문제 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net 알고리즘 - 레드와 블루가 오른쪽과 왼쪽으로 모으는 경우를 생각해서 문제를 수행한다. - 모을 때 뭉텅이가 생기는 경우는 이사 온 볼을 제외한 그다음 볼만으로 모으면 된다. => 그다음 볼들이 있다면 그다음 볼들이 먼저 이동한 후에 첫 번째 볼이 이동하는 것이 최소 횟수이므로. 코드 import sys n = int(sys.stdin.readline()) m = list(map(str, sys.stdin.readline().str..

문제 21758번: 꿀 따기 첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다. www.acmicpc.net 알고리즘 - 벌 - 벌 - 꿀인 경우와 꿀 - 벌 - 벌인 경우와 벌 - 꿀 - 벌인 경우를 나누어 문제를 수행한다. - 벌 - 벌 - 꿀과 꿀 - 벌 - 벌의 경우 첫 번째와 마지막 벌이 먹는 꿀의 양은 고정으로 두고 두 번째 벌이 먹을 수 있는 양을 반복문을 통해 확인하면서 최대 꿀의 양을 비교한다. - 벌 - 꿀 - 벌의 경우 모든 곳에 꿀을 한 번씩 먹고 꿀통 지점의 꿀을 한번 더 먹었을 때에 값을 반복문을 통해 최대 꿀의 양과 비교한다. - 3가지 경우를 확인하고 최대의 꿀의 양을 출력한다. 코드 import sys n = int(sys.stdin.readline()) m = list(ma..

문제 2841번: 외계인의 기타 연주 첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000) 다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수 www.acmicpc.net 알고리즘 - 반복문을 통해 줄의 번호와 프렛의 번호를 입력받아 확인한다. - 주어진 줄의 더 높은 프렛을 누르고 있는 경우에 while문을 통해 손가락을 하나씩 뗀다. - 이미 누르고 있는 줄의 프렛인 경우 패스한다. - 주어진 줄의 프렛이 누르고 있는 프렛보다 높고 같지 않은 경우 프렛을 누른다. 코드 import sys n, p = map(int, sys.stdin.readline().split()) line = ..

문제 1448번: 삼각형 만들기 첫째 줄에 빨대의 개수 N이 주어진다. N은 3보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 빨대의 길이가 한 줄에 하나씩 주어진다. 빨대의 길이는 1,000,000보다 www.acmicpc.net 알고리즘 - 어떤 삼각형도 어는 한 변의 길이가 나머지 두 변의 길이를 합한 것보다 길거나 같을 수 없는 것을 고려햐여 문제를 수행하면 된다. 코드 import sys n = int(sys.stdin.readline()) m = sorted([int(sys.stdin.readline()) for _ in range(n)], reverse=True) answer = -1 # 그 어떤 삼각형도 어느 한 변의 길이가 나머지 두 변의 길이를..

문제 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어 www.acmicpc.net 알고리즘 - 정렬을 통해 문제를 수행한다. - lambda를 통해 문자의 길이, 숫자의 합, 사전 순

문제 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net 알고리즘 - 반복문을 통해 스위치 상태를 변경한다. - 남학생의 경우와 여학생의 경우를 나누어 조건에 맞게 스위치를 변경해준다. - 스위치를 변경 후 상태를 20개씩 출력한다. 코드 import sys n = int(sys.stdin.readline()) state = ["제로"] + list(map(int, sys.stdin.readline().split())) p = int(sys.stdin.readline()) # 반복문을 통해 스위치 상태를 변..

문제 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 www.acmicpc.net 알고리즘 - 반복문을 통해 kim과 lim이 같은 라운드에서 만났을 때를 찾는다. - kim과 lim 앞에 있는 사람들 중 진 사람들을 제외하면 자신의 위치를 찾을 수 있다. - 매번 카운트해준 후 반복문이 종료하면 카운트한 수를 출력한다. 코드 import sys n, kim, lim = map(int, sys.stdin.readline().split()) cnt = 0 # kim과 lim이 같은면 같은 라운드에서 만난 것 while kim != lim: # k..

문제 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 알고리즘 - 이진수를 통해 문제를 해결한다. - bin(n).count('1')은 물병의 개수로 물병의 개수가 k개보다 작을 때까지 반복하여 1L 물병을 구입한다. 코드 import sys n, k = map(int, sys.stdin.readline().split()) cnt = 0 # bin(n).count('1') => 물병의 개수 # 물병의 개수가 k개보다 작을 때까지 반복 while bin(n).count('1') > k: # 1L 물 구입 n += 1..

문제 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net 알고리즘 - 반복문을 통해 모든 좌표를 확인한다. - 현재 좌표에 쓰여 있는 수가 j 축에 또 있는지 확인한다. - 똑같은 수가 있다면 두 좌표를 포함하는 정사각형 좌표가 범위 내에 있고 똑같은 수인지 확인한다. - 똑같은 수라면 길이를 제곱하여 answer에 저장한다. - answer에 최댓값을 출력한다. 코드 import sys n, m = map(int, sys.stdin.readline().split()) graph = [list(map(int ,s..

문제 14247번: 나무 자르기 영선이는 나무꾼으로 나무를 구하러 오전에 산에 오른다. 산에는 n개의 나무가 있는데, 영선이는 하루에 한 나무씩 n일 산에 오르며 나무를 잘라갈 것이다. 하지만 이 산은 영험한 기운이 있어 www.acmicpc.net 알고리즘 - 문제를 해석해보면 모든 나무를 한 번씩 자르는 게 최대 나무 양을 구하는 방법인 것을 알 수 있다. - 나무의 초기 값과 나무가 자라는 수치를 2차원 리스트로 만들어 나무가 자라는 수치를 기준으로 오름차순 정렬한다. - 나무가 자라는 수치가 작은 나무부터 자른다. - 나무의 초기값과 나무가 자라는 수치 x 현재 날짜를 더한 값을 모두 더해 출력한다. - 위 방법보다 더 효율적인 방법으로는 아래 설명에 있다. 코드 (42976KB/120ms) im..