땃쥐네

문제 플랫폼 : 백준 번호 : 02485 제목 : 가로수 난이도 : Silver 4 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 첫 번째 줄에 출력한다 문제 : 링크 생각 문제에서 주어진 예시를 먼저 분석합니다. 1,3,7,13 사이에 나무를 균등하게 심어야하는데 현재 주어진 나무 사이의 간격은 2,4,6입니다. 이들의 최대공약수인 2 간격씩 벌려서 나무들을 배치해주면 나무들을 균등하개 배치할 수 있습니다. 각 구간마다 심어야 할 나무의 갯수는 (각 간격)/(간격간의 최대공약수) - 1 이라는 규칙을 가집니다. 1과 3 사이의 간격은 2이고, 이 사이에는 2/2 -1 = 0개의 나무를 배치하면 됩니다. 3과 7 사이의 간격은 4이고, 이 사이에는 4/2 -1 = 1개의 나무를 배..

문제 플랫폼 : 백준 번호 : 01193 제목 : 분수찾기 난이도 : Silver 5 첫째 줄에 분수를 출력 문제 : 링크 생각 대각선이 가로지르는 방향 단위로 라인(line)을 나눴다. 예를 들면 다음과 같다. - 1번 라인 : 1/1 - 2번 라인 : 1/2 2/1 - 3번 라인 : 3/1 2/2/ 1/3 - 4번 라인 : 1/4 2/3 3/2 4/1 - 5번 라인 : 5/1 4/2 3/3/ 2/4 1/5 각 라인의 규칙을 일반화해보면 다음 규칙을 도출해낼 수 있다. i번 라인에는 i개의 분수가 있다. 짝수 라인은 분자 증가, 분모 감소하고, 홀수 라인은 분자 감소, 분모 증가한다. i번 라인의 분자, 분모의 합은 line + 1과 같다 입력받은 x가 몇 번째 line에 속해있는 지, 그리고 그 라인..

문제 플랫폼 : 백준 번호 : 02798 제목 : 블랙잭 난이도 : Bronze 2 N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력 문제 : boj2798 생각 1. 합을 구해야하는데 3개 숫자를 선택해서 반복을 돌려야하므로 배열에 저장해야한다. 2. 배열의 서로 다른 인덱스에 위치한 숫자 3개를 선택하려면 3중 for문을 돌려야할 것이다. 이렇게 숫자 3개를 구하고 모두 합하는 작업을 반복할 경우 시간복잡도가 O(N3)까지 갈 듯 하다. 3. 반복문을 돌리는 것은 피할 수 없다.하지만 불필요한 반복을 줄일 수 있진 않을까? 4. 3중 반복문을 돌 때 첫번째 반복문, 두번째 반복문 시점에서 여태까지 합산한 값이 m보다 크면 거기서부터는 더..

문제 플랫폼 : 백준 번호 : 01074 제목 : Z 난이도 : Silver 1 N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력 문제 : 링크 필요 지식 분할 정복 풀이 삽질 n = 0 r = 0 c = 0 find = False count = -1 def main(): global n, r, c n, r, c = map(int, input().split()) divide_and_conquer(0, 0, 2 ** n) print(count) def divide_and_conquer(start_r, start_c, length): global count, find if find: return if length == 1: count += 1 if start_r == r and start_c == ..

문제 플랫폼 : 백준 번호 : 02839 제목 : 설탕 배달 난이도 : Silver 4 상근이가 배달하는 봉지의 최소 개수를 출력 문제 : 링크 필요 지식 그리디 알고리즘 : 가능한 많은 5kg 봉지로 포장하고, 나머지는 3kg로 포장하도록 하는 것이 이득이다. 풀이 n = int(input()) a, b = divmod(n, 5) answer = -1 if b == 0: answer = a elif b == 1 and a >= 1: answer = a + 1 elif b == 2 and a >= 2: answer = a + 2 elif b == 3: answer = a + 1 elif b == 4 and a >= 1: answer = a + 2 print(answer) 가능한 많은 5kg 봉지로 포장하..

문제 플랫폼 : 백준 번호 : 02230 제목 : 수 고르기 난이도 : Gold 5 차이가 M이상인 두 수들의 차 중 가장 작은 차이를 출력 문제 : 링크 필요 지식 이분탐색 투 포인터 풀이 입출력 import sys src = sys.stdin.buffer def main(): _, m = map(int, src.readline().split()) nums = sorted(set(int(x) for x in src.read().splitlines())) print(solution(nums, m)) main() 첫 줄 읽기는 sys.stdin.buffer.readline() 나머지 줄 읽기는 sys.stdin.buffer.read().splitlines()를 사용하였다. 이렇게 구한 값들을 int로 변환..

문제 플랫폼 : 백준 번호 : 01865 제목 : 웜홀 난이도 : Gold 3 만약에 시간이 줄어들면서 출발 위치로 돌아오는 것이 가능하면 YES, 불가능하면 NO를 출력 문제 : 링크 필요 지식, 해석 벨먼-포드 알고리즘 출발 정점에서 어떤 정점에 도착하기까지 기껏 많아봐야 N-1번의 간선을 순회하게 된다. 따라서 n-1번 모든 간선을 탐색하면서 이동비용을 최적화시키면 비용이 완전히 최적화된다. 그런데, 음의 사이클이 발생한다면 여기서 한 번 더 간선을 탐색했을 때 비용이 더 줄어드는 지점이 발생한다. 음의 가중치를 간선이 포함됐을 때 음의 사이클 발생여부 감지는 이 방식을 통해 수행하면 된다. 벨먼 포드 알고리즘의 시간복잡도는 O(NE)이다. 문제의 특수성 이 문제는 시작점이 주어지지 않았다. 각 지..

문제 플랫폼 : 백준 번호 : 10815 제목 : 숫자 카드 난이도 : Silver 5 첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력 문제 : 링크 필요 알고리즘 해시 이분탐색 풀이 풀이1 : 해시 import io, os, sys lines = io.BytesIO(os.read(0, os.fstat(0).st_size)).read().splitlines() print = sys.stdout.write a = set(n for n in lines[1].split()) print(' '.join('1' if x in a else '0' for x in lines[3].split())) set에 '상근이'가 가진 카..