ki7348

문제출처: https://www.acmicpc.net/problem/18234 18234번: 당근 훔쳐 먹기 첫 번째 줄에 N(1 ≤ N ≤ 200,000)과 T(N ≤ T ≤ 100,000,000)가 공백으로 구분되어 주어진다. 오리는 당근의 맛을 충분히 높이기 위해 항상 N이상인 T일 동안 재배한다. 다음 N개의 줄에 걸쳐서 i+1번째 www.acmicpc.net 1. 문제 접근 방식 어떻게 풀어야할지 고민을 오래했다. 당근 안먹어도 된다는거 보고 처음엔 그냥 당근 안먹다가 t-n시점부터 증가율이 낮은 순서대로 먹으면 된다고 생각했다. 2. 내가 푼 코드 import sys n, t = map(int,sys.stdin.readline().split()) arr = [] for _ in range(n)..

문제출처: https://www.acmicpc.net/problem/15553 15553번: 난로 첫째 줄에 구사과의 집을 방문하는 친구의 수 N (1 ≤ N ≤ 100,000), 구사과가 가지고 있는 성냥의 개수 K (1 ≤ K ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에는 구사과의 집을 방문하는 친구의 도착 시 www.acmicpc.net 1. 문제 접근 방식 13614번이랑 문제가 비슷했던것 같다. 각 인접한 원소들의 차이값을 새로운 배열에 담고 작은 순서대로 sorting한다. 가장 큰 원소를 k-1번 pop하고 1을 k번 append 해준다음 리스트의 합을 출력한다. 2. 내가 푼 코드 import sys n, k = map(int,sys.stdin.readline().split()) arr ..

문제출처: https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 1. 문제 접근 방식 스위핑 알고리즘을 19598 최소 회의실 개수 문제처럼 풀었다. x와 y가 작은 순서대로 lambda를 이용해 sorting을 하고 end와 cur를 잡고 각각 원소와 비교해가며 바꿔갔다. 처음에 틀렸었는데 5 10 7 35 20 25 이렇게 두번째 원소의 y가 그 다음 원소의 y보다 클 경우도 고려해서 풀었다. 2. 내가 푼 코드 im..

문제출처: https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 www.acmicpc.net 1. 문제 접근 방식 고민을 길게 했다,,, 그러다가 각 인접하는 원소의 크기차이를 배열로 만들고 ex) 1 3 5 6 10이면 ( 2 2 1 4 ) k가 1이면 2+2+1+4 2이면 2+2+1 3이면 2+1 ... 처럼 k값이 한 개 오를때마다 가장 큰 원소를 힙을 이용해서 heappop했다. 2. 내가 푼 코드 import sys import heapq n,k = map(int..

문제출처: https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 1. 문제 접근 방식 배열을 있는 그대로 다 append하면 시간초과 혹은 메모리초과가 발생할 것 같았다. 그래서 최대한 덜 append하는 방법을 생각하다가 첫 행의 원소는 힙에 다 삽일을 하고 두번째 행의 원소부터는 하나씩 꺼내서 heappop한거보다 크면 heappush하고 아니면 원래 heappop한 원소를 다시 heappush하는 방식으로 풀었다. 2. 내가 푼 코드 import sy..

문제출처: https://www.acmicpc.net/problem/7983 7983번: 내일 할거야 내일(1일)부터 연속으로 최대 며칠 동안 놀 수 있는지를 출력한다. 가령, 답이 0이면, 내일 과제를 해야 하며, 1 이면, 모레에 과제를 해야 한다. www.acmicpc.net 1. 문제 접근 방식 처음에는 리스트 두 개를 사용하려고 했는데 메모리 초과가 떴다. 해시함수처럼 입력을 받고 time이라는 변수를 두고 time과 arr[i][1]과의 관계를 따지면서 time값을 초기화 해줬다. 2. 내가 푼 코드 import sys case = int(sys.stdin.readline()) arr = [] for _ in range(case): arr.append(list(map(int,sys.stdin...

문제출처: https://www.acmicpc.net/problem/11497 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 1. 문제 접근 방식 리스트를 큰 순서로 소팅하고 max_num이라는 변수를 선언한다. 리스트의 0번과 1번,2번의 크기를 비교하고 max_num값을 바꿔준다. 나머지 리스트는 2칸씩 띄워가며 비교해준다. ex) 13 10 12 11 10 11 12 인 경우 10 11 12 13 12 11 10 이 가장 차이가 적다고 생각했다. 즉 가장 높은 수를 가운데에 배치하고 양옆으로 그 다음으..

문제출처: https://www.acmicpc.net/problem/17129 17129번: 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유 첫째 줄에 정보섬 2층의 크기 n과 m이 주어진다. (1 ≤ n,m ≤ 3000, 4 ≤ n×m ≤ 9×106) 이후 n행 m열에 걸쳐 0, 1, 2, 3, 4, 5로만 구성된 Ai,j가 주어진다. Ai,j와 Ai,j+1사이에 공백은 주어지지 않는다. 2, www.acmicpc.net 1. 문제 접근 방식 2를 찾아서 BFS를 시작하고 한칸 움직일때마다 전 칸의 +1을 해준다. 이때 만약 3 4 5 를 만나게되고 visited가 False이면 함수를 종료한다. 2. 내가 푼 코드 import sys from collections import deque dx = [-1..

문제출처:https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 1. 문제 접근 방식 1인 원소를 모두 찾아 리스트에 담고 bfs를 돌린다 이때 중요한게 리스트에 담은 원소들을 모두 큐에 넣고 시작한다(1이 두개 이상일 때를 고려해서) 0인 원소를 만날 때마다 값을 1씩 증가시켜준다. 2. 내가 푼 코드 import sys from collections import deque dx = [-1, 1, 0, 0] dy = [0, 0, -1..

문제출처: https://www.acmicpc.net/problem/22352 22352번: 항체 인식 첫 번째 줄에는 SP 촬영 결과의 크기를 의미하는 두 정수 $N$과 $M$이 주어진다. ($1 \le N, M \le 30$) 이는 촬영 결과가 세로로 $N$칸, 가로로 $M$칸 크기의 격자라는 것을 의미한다. 다음 $N$개의 줄에는 www.acmicpc.net 1. 문제 접근 방식 처음 그래프를 순환하다가 다음 그래프와 다른 부분이 생기면 BFS를 사용한다. BFS를 적용한 후에 그래프를 두 개 비교했을때 다른 부분이 있으면 NO를 둘이 같으면 YES를 출력한다. 이때 주의할 것이 BFS를 한번 사용하면 더이상 사용하지 못하고 BFS를 사용할 때 주변에 같은 원소가 있으면 모두 BFS가 적용되어야 한..