https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 우선순위 큐를 이용하는 건데.. 내가 파이썬의 heapq 라이브러리를 착각했다. 우선순위 큐는 정렬이 된 상태랑은 다른 건데 자동으로 정렬이 된다고 생각해서 1차로 틀렸고 그 이후에는 다른 풀이들을 보며 힌트를 좀 참고했다. https://regularmember.tistory.com/142 이 블로그의 설명이 제일 이해하기 쉬웠는데, 이해하고 나니 알겠더라는,,, 근데!!! 파이..
복습
https://www.acmicpc.net/problem/20303 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 그래프 탐색과 배낭 문제를 섞어놓은 문제였다. 1. 일단 주어진 그래프를 DFS로 탐색하여 배열에 [원소의 개수(우는 아이들의 수), 총 캔디 개수] 를 추가하였고 2. 이 배열을 가지고 dp를 활용하여 배낭 문제를 푸는 방식으로 풀었다. dp[i][j] = j 명의 아이들이 울면 어른들이 들킬 때 i번째 배열의..
https://www.acmicpc.net/problem/22116 22116번: 창영이와 퇴근 A1,1에서 AN,N까지, 경로상의 최대 경사의 최솟값을 출력한다. www.acmicpc.net 꽤나 오래 걸린 문제였다.. 처음에는 어라 그냥 BFS로 탐색해도 될 것 같은데..? 하고 풀었더니 시간 초과가 나서.. 우선순위큐와 다익스트라를 이용해서 풀어보려고 했는데 머릿속에서 최단경로(?) 를 구하는 문제와 섞여서 로직을 생각하는 게 어려웠다. 또한 다 구현해놓고 왜 답이 안나오지 하다가.. [N-1][N-1] 에 도착하면 반복문을 종료해야 된다는 걸 뒤늦게 깨달았다.. 이렇게 구현해도 python으로는 시간초과가 났고 pypy3로 통과할 수 있었는데, 100프로에서 인덱스에러가 난 것은 질문 칸에 고마운..
https://www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. N은 100보다 작거나 같으며, M도 100보다 작거나 같다. L은 100보다 크거나 같고, 1000보다 작거나 www.acmicpc.net 예제를 손으로 풀어봤지만,, 아직도 왜 70이 나오는 지 모르겠다,,,ㅋㅋㅋ 코드로 짜서 풀면 70이 나오긴 하는데 말이지,, 휴게소가 없는 구간의 최댓값을 low = 1 , high = L 로 두고 이분탐색을 통해 값을 찾아갔다. 두 지점 사이의 간격이 mid보다 크면 그 사이에 휴게소를 mid보다 작게 될 만큼 세워주고 m에 개수를 더해준다. 그리고 m이 M보다 같거..
https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 이분탐색으로 푸는 방법도 있던데 그 방법은 풀이를 봐도 잘 이해가 되질 않아서 일단 스택으로 풀었다. 더 공부를 해야 할 것 같다. 스택에 0을 미리 넣어놓고, width를 계산할 때 스택에서 pop을 한 후에 i - st[-1] -1 로 계산하는 부분, 그리고 마지막에 인덱스 하나를 더 탐색하는 것이 많이 헷갈렸다.. import sys input = sys.stdi..
https://www.acmicpc.net/problem/2450 2450번: 모양 정돈 첫째 줄에는 모양의 전체 개수 N이 주어진다. N은 3이상 100,000이하이다. 둘째 줄에는 나열된 모양들을 나타내는 N개의 정수가 빈 칸을 사이에 두고 주어지는데, 정수 1은 세모를, 정수 2는 네모를, www.acmicpc.net 어렵다.. 세가지 모양이 있고 각 모양이 적어도 하나 이상 나타나기 때문에 가능한 순서는 3! = 6가지 경우가 있다. 따라서 이 6가지 경우를 모두 보면서 각각의 이동횟수 중 최소를 출력하면 된다. 이동횟수를 구하는 방법은 더 어려웠다.. 검색해보니 대충 이해가 될 듯 한데 명확히 왜 그게 맞는지를 설명을 못하겠다. 어렴풋이 이해가 되는 정도..? 그냥 아예 확 외워버리는 게 나을수..
https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 3월 1일을 포함하는 날짜를 가진 꽃 중에 지는 날이 제일 먼 꽃을 선택하여 그 꽃이 지는 날을 다시 시작날짜로 놓고, 이 과정을 반복해서 시작 날짜가 11월 30일보다 커지면 ans를 출력한다. 비교를 쉽게 하기 위해 날짜를 숫자로 변환한다 ex) 3월 1일 = 301, 11월 30일 = 1130 또한 정렬을 통해 O(N)시간 안에 탐색이 가능하도록 한다. 꽃 배열을 돌다가 ..
https://www.acmicpc.net/problem/2180 2180번: 소방서의 고민 첫째 줄에 화재 발생 건수 n이 주어진다. n은 200,000 이하의 양의 정수이다. 둘째 줄부터 n개의 줄에 각각 한 줄에 한 쌍씩 a와 b가 입력된다. a와 b는 40,000 이하의 음이 아닌 정수이다. www.acmicpc.net a가 제일 큰 화재부터 먼저 진압하고, a가 같은 경우에는 b가 작은 화재부터 먼저 진압한다.. 예제도 모두 맞는데, 시간초과가 난다.... c++로 갈아탄 후에는 틀렸습니다. 가 나오는 걸로 봐서는 이렇게 풀면 안되나 보다.. 내가 c++을 잘 몰라서 틀린 걸 수도.. 아무튼 수식으로 정리를 해서 풀었다.. b/a < d/c 로 했더니 또 틀렸습니다.. 나와서 곱셈으로 바꿔서 했..
https://www.acmicpc.net/problem/15811 15811번: 복면산?! 복면산이란 수학 퍼즐의 일종으로, 어떤 계산식의 각 숫자들을 특정 문자로 바꾸면 각 문자가 어떤 숫자인지 맞추는 퍼즐이다. 대표적으로 SEND+MORE=MONEY가 있다. SEND + MORE ------ MONEY S=9, E=5, N=6, D=7, www.acmicpc.net DFS 재귀를 이용해서 구현을 했는데 시간초과가 났다. 아예 처음부터 순열을 구해서 부르트포스로 풀면 되는 문제였다. 처음에 접근할 때는 넣을 때부터 덧셈의 결과를 맞춰보려고 생각하다가 막혔는데.. 너무 어렵게 생각했던 것 같다. 각 문자마다 다른 숫자여야 하므로 전체 문자의 개수를 구해 0~9까지 그 개수에 맞게 순열을 뽑으면 된다. ..
https://www.acmicpc.net/problem/2026 2026번: 소풍 만약 K명의 친구 관계인 학생들이 존재하지 않는다면 -1을 출력한다. 그 외의 경우에는, K개의 줄에 학생들의 번호를 증가하는 순서로 한 줄에 한 개씩 출력한다. 여러 경우가 존재한다면 첫 번째 www.acmicpc.net 백트래킹 문제가 항상 어렵다... 재귀 싫어.... 일단 재귀를 사용할 때는 먼저 탈출조건을 적은 후에 차근차근 생각하면 될 것 같다. 1. 먼저 조건을 체크하고, 조건에 맞으면 ans에 추가한다. 2. ans의 길이가 K가 되면 끝낸다. 3. dfs에서 탈출했을 때 pop해야한다. import sys input = sys.stdin.readline K, N, F = map(int, input().sp..
