문제 https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 설계 N = int(input()) if N == 1: print(1) else: now, next = 0, 1 for i in range(N-1): now, next = next, now + next print(next) - 한줄로 적지 않으면 먼저 복사된 now가 계산되므로 동시에 연산해야한다. # 다음 숫자가 복사된다. for i in range(N-..
문제 https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 설계 - bfs로 연결되어있는 색상 개수 count def bfs(x, y, team): global visit, arr visit[x][y] = 1 q = [(x, y)] score = 1 # bfs 들어오자마자 1칸 체크 while q: x, y = q.pop(0) for i in range(4): dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1..
문제 https://www.acmicpc.net/problem/1758 1758번: 알바생 강호 첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같 www.acmicpc.net 설계 - 가장 큰 수가 앞으로 오도록 내림차순으로 정렬, 가장 큰 점수의 손실을 최대한 줄이는 방법을 선택했다. N = int(input()) arr = [int(input()) for _ in range(N)] arr.sort(reverse=True) tips = 0 for i in range(N): if arr[i] - i < 0: pass else: tips += (a..
문제 https://www.acmicpc.net/problem/9342 9342번: 염색체 상근이는 생명과학 연구소에서 염색체가 특정한 패턴인지를 확인하는 일을 하고 있다. 염색체는 알파벳 대문자 (A, B, C, ..., Z)로만 이루어진 문자열이다. 상근이는 각 염색체가 다음과 같은 규칙 www.acmicpc.net 설계 - 조건들을 순서대로 정의한다. - 첫번째 알파벳이 A, F, C가 아닌 경우 제거한다. N = int(input()) arr = [list(input()) for _ in range(N)] index = ['A', 'B', 'C', 'D', 'E', 'F'] condition = ['A', 'F', 'C'] for i in range(N): cnt = 0 # 규칙을 몇번 통과했는지..
문제 https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 설계 - 조합 라이브러리를 사용했다. # 로또 from itertools import combinations while 1: arr = list(map(int, input().split())) if arr == [0]: # 0이 나올 경우 종료 break N = arr[0] # 개수인 N 저장 후 빼내기 arr.pop(0) for i in combinations(arr, 6): p..
문제 https://www.acmicpc.net/problem/10798 10798번: 세로읽기 총 다섯줄의 입력이 주어진다. 각 줄에는 최소 1개, 최대 15개의 글자들이 빈칸 없이 연속으로 주어진다. 주어지는 글자는 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’ www.acmicpc.net 설계 - 주어지는 단어는 5개이지만 각 단어의 길이는 다를 수 있다는 점을 주의하자 # 세로읽기 arr = [list(input()) for _ in range(5)] maxN = 0 for i in range(5): # 한줄에 최대 몇글자인지 확인 maxN = max(maxN, len(arr[i])) for i in range(5): # 비어있을 경우 빈칸 삽입 while len(a..
문제 https://www.acmicpc.net/problem/1417 1417번: 국회의원 선거 첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어온다. N은 50보다 작거나 같 www.acmicpc.net 설계 - heap을 음수로 변환하여 0번째 index와 비교한다. - heap 구조상 0번째 노드의 정렬은 언제나 보장되지만, 그 뒤는 정렬이 되어있지 않을 수 있기 때문이다. # 국회의원 선거 from heapq import heappop, heappush, heapify N = int(input()) heap = [int(input()) for _ in range(N)] vot..
문제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 설계 - 첫번째 조건 : 회의가 빨리 끝날수록 뒤에 회의를 많이 잡을 수 있기 때문에 회의가 빨리 끝나는 시간을 최우선으로 정렬한다. - 두번째 조건 : 회의 시간이 (1, 3), (3, 3)일 경우 먼저 1시에 회의를 먼저 하고 끝내야 3시 회의를 하여 회의를 2번 할 수 있다. 때문에 회의 종료시간이 같을 경우 빨리 시작하는 기준으로 정렬한다. - 위 두가지 조건을 모두 종합했을 때 시작시간 기준 정렬 → 종료시간 기준 정렬을 해야만 우리가 원하는 위 두가지 조건을 만족시킬 수 있다. N = int(in..
문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 설계 - 보통 이분탐색은 최소한의 횟수로 목표를 찾는 것이다. - 이번 문제는 공유기를 설치할 거리를 이분 탐색으로 결정하여 공유기 사이의 거리가 mid값 이상인 경우 공유기를 설치할 수 있다. - mid값 이상의 간격으로 공유기를 설치했을 때 공유기의 개수가 모자라다면 mid 값을 줄여주고, 설치해야하는 공유기의 개수가 너무 적다면 mid..
문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 설계 - flood fill - 토마토가 모두 익는 최소 날짜를 구하여야 하기에 DFS도 생각해봤으나 N, M의 수가 너무 커서 불가능 - flood fill을 이용하여 아직 익지 않은 곳에 이전보다 1 큰 숫자를 누적하며 넣어주고 마지막에 max 값을 찾아 소요일을 확인한다. - 생각보다 코드가 길게 나왔다. 다음에는 더 줄이도록 해봐야겠다. from collections ..
