네발로 코딩하는 포메라니안

1. 문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 2. 풀이 과정 필요한 개념 : 조합, BFS 3개의 벽을 어디 세울지에 대해 조합을 사용하고, virus가 퍼지는 과정을 BFS를 통해 수행한다. 방법1) 재귀를 이용한 조합 import sys, copy, collections input = sys.stdin.readline n, m = map(int, input().split()) dx = [-1, 0, 1, 0] dy = [0, 1, 0, -..

1. 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 2. 풀이 과정 import sys from collections import deque input = sys.stdin.readline n, m = map(int, input().split()) dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] q = deque() graph = [] for i in range(m): graph.append(list(..

1. 문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 2. 풀이 과정 방법1) deque 라이브러리 활용하기 from collections import deque n, m = map(int, input().split()) miro = [list(map(int, input())) for _ in range(n)] dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] #BFS => 최단 거리 def bfs(graph): q = deque() q.append((..

1. 문제 https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 2. 풀이 과정 1~n까지의 합 = n(n+1)/2 이므로 n(n+1)/2 ≤ (입력값)을 만족하는 n의 최댓값을 구하면 된다. n(n+1)/2 ≤ (입력값) => n(n+1) ≤ 2*(입력값)이다.여기서 n(n+1)은 n*n < n(n+1) < (n+1)(n+1)을 만족한다. 모든 항에 루트를 씌우면, n < ${(n(n+1))}^.5$ < n+1이 된다. int형으로 바꾸면 소수점을 버리니 n을 반환할 수 있으며, ${(n(n+1))}^.5$ ≤ 2*(입력값)이므로 n+1을 반환할 수도 있다. 따라서..

1. 문제 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 2. 풀이 과정 방법1) (물건의 무게)/(로프의 수) ≤ (로프가 견딜 수 있는 무게) = (물건의 무게) ≤ (로프가 견딜 수 있는 무게)*(로프의 수) n = int(input()) rope = [int(input()) for _ in range(n)] rope.sort(reverse=True) result = 0 for i in range(n): #로프 최소 무게 * 개수

1. 문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 2. 풀이 과정 주어진 식에서 빼기가 있다면 괄호를 묶어 뒤에 나오는 모든 수를 빼기 연산으로 만들 수 있다. 따라서 식의 값을 최소로 만드는 방법은 식에서 처음 나오는 빼기 뒤의 수들을 모두 뺄셈 연산을 수행해주면 된다. 예) 50+10-30+10+20-30+10 = 50+10-(30+10+20)-(30+10) 으로 묶어보면 분배 법칙을 통해 '-'를 다 적용해줄 수 있다. s ..

1. 문제 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 2. 풀이 과정 n, k = map(int, input().split()) cost = [int(input()) for i in range(n)][::-1] result = 0 for i in cost: result += k//i; k = k%i print(result)

1. 문제 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 2. 풀이 과정 *Key : 에라토스테네스의 체 (소수인 수만 남기기) 1) 두 수의 차이 크기인 배열을 생성한다. 5, 10는 배열에서 각각 -5를 해서 0, 5 인덱스를 사용한다. 2) 소수를 구하는 방법은 에라토스테네스의 체를 이용한다. *에라토스테네스의 체란? n의 제곱수 이하인 수중에서 소수를 찾아서 그 소수의 배수를 제거하면 n 이하에 있는 소수를 구할 수 있다. 자세한 설명은 아래의 사이트를 이용하였다. ..

1. 문제 https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net > 증가량은 한 번에 1만큼 증가 및 감소가 가능하다. 유지도 가능 > 1로 시작해서 1로 끝나야 한다. 2. 풀이 과정 *Key : 최소한의 작동 횟수 = 한 번에 갈 수 있는 거리를 최대로 해야 한다. 1) 유지하는 경우를 제외하고 생각했을 때 1, 2, ... ,n-1 , n , n-1, ... , 2, 1 의 형태가 최소한의 횟수로 도..

1. 문제 https://www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) www.acmicpc.net 2. 풀이 과정 *Key : 마지막 단계에는 정상에 올라가면 내려올 필요가 없다. 시간제한 주의 1) 마지막 단계 전까지 날짜를 계산한다. day = (top-plus)/pminus;//pminus는 (올라가는 거리)-(미끄러지는 거리) 2) 마지막 단계 전까지 올라간 거리를 계산한다. top-day*pminus 3) 남은 거리가 올라갈 거리보다 크면 +2일, 작으면 +1일을 한다. [전체 코드] import java.io.BufferedRea..