https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 메모리 제한(4MB)이 있는 dp문제 아이디어 1. 메모리 제한 매우 적은 메모리 제한을 보고 dp를 사용하기로 결정 단순히 문제에 주어진 N값만 보고 배열을 만들기엔 4MB로는 턱없이 부족하다. 따라서 임시로 저장해주는 변수를 따로 만들어 사용 코드 설명 max_arr = [int(x) for x in sys.stdin.readline().rstrip().split()] min_arr = copy.copy(m..
https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 아이디어 1. bfs 주사위를 선택(1 ~ 6)할 수 있는 점과 최단 횟수를 구해한다는 점에 bfs를 선택 뱀과 사다리만 잘 체크해주면 되는 문제. 코드 설명 deq = deque() deq.append([1, 0]) visited[1] = True while deq: po, count = deq.popleft() if po == 100: print(..
https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 오랜만에 부분점수가 있는 문제 아이디어 1. 가장 먼저 떠오른 건 슬라이싱 단순하게 생각해서 그냥 Pn 크기만큼 잘라서 탐색했다. 아이디어가 너무 쉬운만큼 부분점수 50점만 줬다. 2. 시간 초과를 피하려면 이번에 알게 됐는데, 파이썬에서 arr [a:b]의 시간 복잡도는 O(b - a)라고 한다. 슬라이스를 최대한 덜 쓰고 반복..
https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 아이디어 1. 조합 처음에 문제를 봤을 때 방법을 몰라서 조합 라이브러리를 사용함. 테스트 케이스와 n의 최대가 적어 가능할 거라 생각했지만 다시 생각해보니 조합이면 경우의 수가 엄청 많아지니 시간 초과가 떴다. 2. 수학 어릴 때 배웠던 경우의 수 문제를 생각하면 금방 풀 수 있다. 딕셔너리와 같이 쓰면..
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/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 아이디어 1. 두 가지로 나눠 생각하면 테트로미노 도형 만들기 종이 위에 올리기 2. 도형 만들기 도형이 회전이나 대칭도 가능하니 dfs를 사용하면 T도형 빼고 전부 다 만들 수 있다. dfs 탐색 깊이를 4까지 설정하면 도형을 확인할 수 있다. T 모양은 따로 함수를 만들어 처리했다. 3. 종이에 도형 놓기 시간제한이나 N, M 크기를 보고 브루트 포스를 사용하기로 결정했다. 각 위치마다 만들어..
https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 아이디어 1. 알고리즘 선택 처음 문제를 보고 DP로 풀어야 하나 생각하면서 도저히 모르겠어서 알고리즘 분류를 보니까 그냥 브루트 포스 문제다. 2. 구현 먼저 현재 채널(100)에서 최소값이 나올 수 있는지 확인 이후 0부터 1000000까지 버튼으로 만들 수 있는 채널인지 확인 그 채널 숫자를 만드는데 필요한 버튼 개수 확인 코드 설명 N = int(input()) M = in..
