https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 아이디어 1. bfs 이미 숨바꼭질 1과 3을 풀어서 대충 알고 있다. x - 1, x + 1, x * 2 큐에 넣어주면서 탐색하면 됨. 경우의 수를 어떻게 구할지 생각만 하면 된다. 2. 경우의 수 쭉 탐색을 하다가 맨 처음 동생한테 도착한 시간을 저장하고 이후 동생한테 도착했을 때 저장해둔 시간과 같다면 경우의 수를 +1 해준다. 전체 코드 from col..
https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 아이디어 1. 반복문 문제 느낌이 진실을 아는 사람이 좀비같이 감염시키는 것이라 생각 그래서 진실을 아는 사람과 같이 있는 사람들을 진실을 아는 사람으로 바꿨다. 근데 이러면 진실을 아는 사람들이 바뀌어서 전체 파티를 또 탐색해야 하고 이를 계속 반복해야 해서 실패했다. 2. 그래프 그러다가 동시에 한 번에 해야 된다는 것을 깨닫고 그래프를 사용하기로 결정 각 파티마다 있는 사람들을 두 명씩 양방향으로 이어..
https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 아이디어 1. 조합 단순하게 리스트에 있는 값 중에서 두 개를 뽑아 계산하는 코드를 짰다. 시간 초과 발생 생각해보니까 조합이면 100000C2인데 1초로는 택도 없다. 2. 문제에 오름차순이 힌트 미리 정렬이 되어있으니까 이걸 이용하라는 의미로 해석 이분 탐색과 비슷하게 좌우에서 하나씩 좁혀가며 최솟값(0에 가까운 값)을 찾기로 결정. 코드 설명 while l < r: cur_value =..
https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 아이디어 1. 시간 초과 처음에는 x, y값이 나올 때까지 1씩 더해가며 count를 했다. 숫자가 반복되면 -1을 출력하게 했다. 생각이 너무 쉬웠는지 시간 초과가 발생했다. 다른 방법을 사용하기로 결정 코드 설명 def find_K(M, N, x, y): K = x while K
https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 아이디어 1. 플로이드 와샬 예전에 가중치가 있는 플로이드 와샬을 푼 경험이 있어서 이번에는 간단하게 해결했다. 기존 알고리즘에서 약간만 변형하면 됨 코드 설명 for k in range(N): for i in range(N): for j in range(N): if adj_matrix[i][k] == 1 and adj_matrix[k][j] == 1: adj_matrix[i][j] = 1 k는 거쳐가는 노드, i는 시작 노드, j는 도착..
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..
