Simple Explain

#1931번 회의실 배정 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 회의 시작 시간과 종료 시간이 주어지면, 최대한 많은 회의를 진행하는 경우에 몇 개의 회의를 진행할 수 있는지를 출력하면 된다. 처음에 나는 모든 경우의 수를 다 계산하려 했다. 근데 시간초과가 났다. 여러 방법을 추가했지만 시간초과였다. 정답은 굉장히 단순했다. 그냥 정렬하고 순서대로 계산하면 된다. task = [list(map(int, input().split())) for _ in range(int(input()))] task = sorted(task, key=lambda a: a..

#16953번 A -> B https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net A 라는 수를 1. 2를 곱한다 2. 1을 수의 오른쪽에 추가한다 라는 두 가지 연산을 이용해서 B라는 수로 만들 때, 연산횟수를 출력하면 된다. 처음에는 DP라고 생각했었는데, 알고보니 BFS였다. (아마 연산의 종류가 두 가지이기 때문이 아닐까..?) 틀린코드 from collections import deque A, B = map(int, input().split()) visited = [False]*(B+1) que = deque() que.append(A) visited[A] = 1 w..

#1764번 듣보잡 https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 처음에 대충 풀었더니 시간초과나길래 고민을 좀 했다. 딕셔너리에서 key로 값을 호출하는 시간복잡도가 O(1)이길래 딕셔너리를 활용했다. N, M = map(int, input().split()) nonlisten = dict() for _ in range(N): nonlisten[input()] = False for _ in range(M): try: s = input() ..

#18111번 마인크래프트 https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 어떻게 구현해야하는지 떠오르지않아서 다른 자료들을 조금 참고했다. 브루트포스로 구현해야하는데, 탐색 높이의 범위를 설정하는 방법이 헷갈렸다. 탐색범위는 주어진 높이 중 최소높이부터 최대높이까지 진행하면 된다. 시간초과로 머리아팠지만 pypy3제출로 해결 파이썬으로 그리디 혹은 브루트포스를 제출하는건 늘 시간초과가 나는듯 하다. from sys import stdin i..

#4949번 균형잡힌 세상 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net 처음엔 쉬울거라 생각했지만,... 괄호를 판단하는 방법이 기억이 나지않나 과거 코드를 복기했다. def check(ps_string): tmp = ps_string.split("()") tmp = "".join(tmp) tmp = tmp.split("[]") tmp = "".join(tmp) if len(tmp) < len(ps_string): return..

#1654번 랜선 자르기 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 이분탐색이란 눈치를 채고 바로 풀었다 틀린코드 K, N = map(int, input().split()) lans = [int(input()) for _ in range(K)] start = 1 end = min(lans) while start N: start = mid + 1 elif pivot < N: end = mid - 1 바로 틀리길래..

14442번 벽 부수고 이동하기 2 https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 유사 문제가 존재하고, 풀어본 경험이 있어 금방 눈치챌 수 있었다. https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, ..

#16946번 벽 부수고 이동하기 4 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 내 첫 접근방법은 벽을 기록해놓은 뒤, 벽을 순회하면서 인접한 0을 세는 방식이었다. 틀린코드 from collections import deque N, M = map(int, input().split()) maps = [] walls = deque() for i in range(N): tmp = input() l = [] for j in..

#2206번 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 굉장히 단순한 bfs문제라고 생각하고 풀었다. 틀린코드 from collections import deque # 벽을 부술 수 있는지 여부를 boolean으로 전달하기. # 상하좌우 이동 # 막히면 끝 # 최단경로 -> bfs # 0,0 -> N,M N, M = map(int, input().split()) maps = [[int(x) fo..

#12886 돌 그룹 https://www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려 www.acmicpc.net 굉장히 쉬워보였지만 쉽지않았다. dfs, bfs 모두 가능해보였지만 비교적 쉬운 bfs로 접근했다. 문제는 방문기록을 어떻게 하느냐 였는데 처음에는 3차원 리스트를 생각했었다. (값이 3개이기 때문에) 다시 한번 생각해보자 문제에서는 두 값을 선택한 뒤 큰 값에서 작은 값을 빼고 작은 값을 두배로 한다. 즉, 전체 돌의 갯수는 변하지 않는다. -> 이게 핵심이다. 이 때..