https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 아이디어 1. 그리디와 dp 처음에는 n을 넘지 않는 최대 제곱수를 n에 빼가면 되지 않을까 생각했다. 이렇게 하면 예외가 생긴다. 예를 들어 12는 그리디로 생각하면 9, 1, 1, 1이지만 정답은 4,4,4로 3개가 최소 개수다. 다시 문제 내용을 보고 dp로 풀기로 결정 DP[n] = (n이라는 수를 만드는데 필요한 수의 개수) 코드 설명 k = 1 whi..
https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net DP 너무 어렵다에요 아이디어 1. DP 문제를 보고 dp문제인 것도 알고 'DP [k] = 합이 k가 되는 경우의 수'라는 것도 알았다. 근데 점화식 아이디어가 떠오르지 않아 검색의 힘을 빌렸다. 일주일 뒤에 또 풀어봤는데 또 까먹었다. 이해를 못 했다는 뜻이다. 이번 기회에 제대로 이해하고 넘어가기로 함. 코드 설명 DP = [0] * (k + 1) DP[0] = 1 for c in coins:..
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문이나 리스트를 사용해 시간제한이 걸린 거 같다..
