![]()
https://www.acmicpc.net/problem/1245 1245번: 농장 관리 첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수 www.acmicpc.net 1. BFS 산봉우리들을 세는 문제이다. 좌표는 상하좌우 + 대각선, 총 8방향으로 인접한 칸이면 이동할 수 있으며, 높이 값이 0 이면 산봉우리가 아니다 !!! 따라서 bfs 탐색 또한 높이가 0 보다 클 때만 처리했다. bfs에서 , 현재 확인중인 array[x][y] 값을 중심으로, 자기자신 보다 높은 위치를 만나면 (x, y) 에 해당하는 봉우리 라인은 산봉우..
![]()
https://www.acmicpc.net/problem/10836 10836번: 여왕벌 입력의 첫 줄에는 격자칸의 가로와 세로 크기 M(2 ≤ M ≤ 700)과 날짜 수 N(1 ≤ N ≤ 1,000,000)이 자연수로 주어진다. 첫날 아침의 애벌레 크기는 모두 1이므로 입력에 주어지지 않는다. 다음 N개의 www.acmicpc.net 이 문제는 구현/시뮬레이션 유형이지만 한편으로는 greedy 알고리즘으로 규칙을 찾아야 한다. 핵심 아이디어는 다음과 같다. 왼쪽 아래에서부터 위, 오른쪽 방향으로 성장한 애벌레의 값을 갱신해주는데, 이 화살표 순서대로 숫자가 작아지지 않는다고 했으므로, 갱신되지 않은 (m-1) * (m-1) 칸들의 값은 자기자신의 바로 윗칸의 값을 가져오면 된다. 즉 자기자신의 바로 윗..
https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 진입차수가 0 이면 queue에 넣어주고, queue에서 빼서 현재 노드 탐색하고, 현재 노드에서 인접한 노드들의 진입차수를 1씩 뺸다. 그리고 진입차수가 0이 되면 다시 queue에 넣어준다. 현재 최소 학기를 구해야 하므로 , queue에 enqueue하는게 몇번째인지 세어주는 count 도 같이 넣어준다. from collections import deque n, m = map(int, input().split()) ..
https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 숨바꼭질 1 번문제와 문제는 같은데, 업그레이드 된 부분은 수빈이가 동생을 찾을 수 있는 가장 빠른 시간에 대한 경로를 저장해두어야 한다는 것이다. 경로 저장을 위해 note라는 배열을 생성한다. for nx in [now-1, now+1, now*2]: if 0
https://www.acmicpc.net/problem/22869 22869번: 징검다리 건너기 (small) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으 www.acmicpc.net 징검다리 건너기 (large) 문제와 거의 동일하게 풀었다. 다만 마지막에 dp[-1] 칸이 값이 k보다 작거나 같은지 확인해주면 된다. import sys input = sys.stdin.readline n, k = map(int, input().split()) array = list(map(int, input().split())) I..
https://www.acmicpc.net/problem/20444 20444번: 색종이와 가위 첫 줄에 정수 n, k가 주어진다. (1 ≤ n ≤ 231-1, 1 ≤ k ≤ 263-1) www.acmicpc.net i) 규칙 찾기 n=4일때 가능한 모든 경우를 보면 (col, row) = (0, 4), (1, 3), (2, 2) (3, 1), (4, 0) 이다 근데 column , row 구분을 안해줘도 되는 이유가, 만들어지는 색종이의 개수만 확인하면 되기 때문이다. -> 즉 0 부터 n//2 까지의 경우만 확인해주면 시간을 줄일 수 있다. 만들어 지는 색종이의 개수는 (col+1) * (row+1) 이다. 또한 찾을 수 있는 규칙은, column 개수와 row의 개수 차이가 클수록 만들어지는 색종이..
![]()
https://www.acmicpc.net/problem/20164 20164번: 홀수 홀릭 호석 호석이는 짝수랑 홀수 중에서 이니셜이 같은 홀수를 더 좋아한다. 운전을 하던 호석이는 앞차의 번호판이 홀수로 가득할 때 사랑스러움을 느낄 정도이다. 전화번호도 홀수만 있고 싶다. 그렇게 www.acmicpc.net 구현문제이다 또한 별 다른 알고리즘 없이, 세자리 이상인 경우에도 가능한 숫자 조합을 이중 for문으로 모두 만들어 주고 다시 호출했다 그렇지만...!! 내가 놓친부분은 바로 새로운 숫자 조합을 만들 때에도 홀수의 개수를 세는 것이다 ... def check_odd(n): # 1. 각 자리 숫자 중 홀수의 개수를 적는다. temp = 0 for i in n: if int(i) % 2 == 1: t..
https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net ㅎㅎ 이분탐색으로 쉽게 풀리는 문제이다 ~ 다만 target 이 되는 숫자는 당연히 조합에 사용하지 못하므로 index를 조절해주는 것이 필요하다 ~~ n = int(input()) array = list(map(int, input().split())) array.sort() answer = 0 def solve(target): global answer left, right = 0, n - 1 while left < righ..
