https://www.acmicpc.net/problem/28250 28250번: 이브, 프시케 그리고 푸른 MEX의 아내 첫째 줄에 정수 $N$이 주어진다. ($2 \le N \le 200\,000$) 둘째 줄에 $N$개의 정수 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. ($0 \le A_i \le 100\,000$) www.acmicpc.net 문제 이름이 특이해서 풀어본 문제. 실2라고 얕잡아봤다가 끔찍한 결과가 나왔다. 실제 코테였다면 풀었을지 장담 못하겠다. 꼭 입력값 제한을 보면서 시간을 추측하는 습관을 들이자. 여담이지만 코테 환경을 상상하며 문제를 푸는 건 도움이 되는 거 같다. 아이디어 1. 이중 for문 실패 수식을 보고 무식하게 이중 for으로 구현했다가 ..
https://www.acmicpc.net/problem/28017 28017번: 게임을 클리어하자 첫째 줄에 산지니가 게임을 몇 회차를 하는지 나타내는 수 $N$과 무기의 종류 $M$이 공백으로 구분되어 주어진다. $(2 \le N, M \le 500)$ 둘째 줄부터 $N$개의 줄에는 각 무기마다 게임을 클리어하는데 www.acmicpc.net 대회 초반에 삽집하다가 DP인걸 깨닫고 해결했다. pypy로 제출, 이후 python으로 다시 제출. 아이디어 1. 반복문 단순 반복문으로 작성했다 실패했다. 2. DP n회차의 각 무기마다 올 수 있는 시간을 저장하면 된다. 위 이미지처럼 이전 행에 있는 값 중 최솟값을 다음 행에 더해가며 업데이트하면 된다. 최종적으로 마지막 행의 최솟값을 출력하면 된다. 전..
https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 처음에는 itertools 라이브러리를 사용하여 순열을 구하고, 각 순열마다 검사하는 방법으로 했는데 시간초과 되었다. 생각해 보면 최대 경우가 15P15까지 나오므로 이 방법은 당연히 아니었다. 암호를 판별하는 방식이 아닌 처음부터 암호를 조건에 맞게 만드는 방법으로 문제를 풀어 해결하였다. 아이디어 1. 암호 조건 암호에 있는 알파벳을 증가하는 순서(aescend)로 배열되었다. 암호에는 모음 1개..
https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 조건만 잘 생각하면 되는 착한 문제. 아이디어 1. 다익스트라 출발지로 부터 최단거리를 계산해서 수색 범위안에 들어가는지 확인하면 된다. 수색 범위안에 들어오면 아이템 개수를 더해주면 된다. 1 ~ n까지 for문으로 출발지를 바꾸면서 탐색하면 된다. 2. 플로이드 워셜 지역의 개수(100)가 적으므로 플로이드 워셜로 풀어도 시간초과에 걸리지 않는다. 전체 코드 다익스트라 import heapq imp..
https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net ZZZ 아이디어 1. 숫자를 어떻게 찾지 처음에는 배열을 만들어보려 했으나 최대길이가 2^15인걸 보고 접었다. 분할 탐색같이 생겼지만 혹시 다른 방법이 있을까 봐 고민하다가 그냥 분할 정복으로 풀기로 했다. 2. 규칙을 찾아야 해 문제에서 주어진 그림을 보면 4등분 했을 때 느낌이 온다. 4등분 했을때 각각의 첫 번째 요소가 일정한 규칙이 있다는 게 보인다. 예를 들어 N = 3으로 주..
https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 아이디어 1. bfs 최소한의 명령 어을 출력 하라 했으므로 bfs가 아니면 못 풀 거 같다고 생각했다. 시간제한도 6초로 넉넉하게 있어서 충분하다고 생각했다. 2. 시간 초과 요즘 계속 시간 초과가 뜬다. 6초라서 넉넉할 줄 알았는데. 시간 초과가 뜬이유는 다음과 같다. D, S, L, R 각각의 명령어를 간소하게 구현해야 했는데, if문이나 리스트를 사용해 시간제한이 걸린 거 같다..
https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 구역의 수를 찾는 문제 근데 이제 색약을 곁들인 dfs나 bfs 중 하나를 택해 문제를 해결하면 된다. 해결하는 방법이 정말 다양하지만 그중 하나만 작성함. 문제 풀이 이 문제는 색약일때와 색약이 아닐 때 각각 어떻게 처리하냐에 풀이가 다를 것이다. 나는 배열을 복사해서 색약일 때(R == G) 따로 함수를 만들어 탐색하도록 만들었다. 다른 방법으로는 색약이 아닌 경우 탐색을 해주고 원래 ..
https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 어린이에겐 매우 어려운 게임이다. 시간제한이 0.1초 인걸 보니 기존 정렬 방식으로는 해결이 힘들 거 같다. 사실문제 풀기 전에 우선순위 큐 문제 인걸 알고 있어서 이걸 어떻게 적용할지 생각하면 되는 문제다. 우선순위 큐 문제는 내가 정한 우선순위가 높은 데이터가 가장 먼저 pop 되는 큐다. 근데 예제 출력 부분을 보면 1 1 2 2 같이 중복된 값이 여러 번 출력된다. 따라서 ..
