https://www.acmicpc.net/problem/2155 2155번: 삼각형의 최단 경로 첫째 줄에 두 정수 A, B(1≤A, B≤1,000,000,000)가 주어진다. www.acmicpc.net 문제풀이: 어떻게 풀어야 하는 지 도무지 모르겠었는데..(사실 생각하기 귀찮아서 미뤄뒀던 걸수도..) 동아리 부원이 푼 걸 보고 힌트를 얻었다! 엄청난 삽질.. 까진 아니고 알고 나니 아.. 하는 그런 문제였다. 이렇게 푸는 게 정석일 지는 모르겠지만.. 루트 즉, 1번 위치부터 각 번호까지의 최단 경로를 구해보면 0 2 1 2 4 3 4 3 4 6 5 6 5 6 5 6 이렇게 나온다! 이 규칙은 쉽게 구할 수 있으니 이렇게 구해서 큰 수에서 작은 수를 빼주기만 하면 되는 것.. import sys ..
분류 전체보기
https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 문제풀이: 플로이드 와샬 알고리즘을 사용하여 문제를 풀었고, pypy로 통과했다. 플로이드 와샬 알고리즘을 사용해야겠다고 생각하는 게 어려운 것 같다. import sys V, E = map(int, sys.stdin.readline().split()) INF = 10**10 graph = [[INF]*(V+1) for _ in range(V+1)] for _ i..
https://www.acmicpc.net/problem/14496 14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1
https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 문제 풀이: BFS를 사용해서 그래프를 탐색하면서 최단 거리를 dist[] 배열에 저장하였고, 탐색이 끝난 후에 dist 배열을 돌면서 값이 K인 경우를 출력하였다. K인 경우가 없을 때는 -1을 출력하였다. import sys from collections import deque N, M, K, X = map(int, sy..
www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net dfs와 백트래킹을 이용하여 풀었는데 왜 틀리다고 나올까.. 삽질하다가 마지막에 시작했던 노드로 다시 돌아오는 부분을 검사할 때 cnt==3이라고 조건을 달아둔 걸 발견했다. 당연히 N-1이라고 해야 하는 것을ㅠㅠ import sys N = int(sys.stdin.readline()) W = [] for _ in range(N): W.append(list(map(i..
www.acmicpc.net/problem/19621 19621번: 회의실 배정 2 서준이는 아빠로부터 N개의 회의와 하나의 회의실을 선물로 받았다. 각 회의는 시작 시간, 끝나는 시간, 회의 인원이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, www.acmicpc.net 임의의 회의 K(1≤ K ≤ N)는 회의 K − 1과 회의 K + 1과는 회의 시간이 겹치고 다른 회의들과는 회의 시간이 겹치지 않는다. 이 조건 때문에 dfs로 구현하여 풀 수 있다. K번째 회의를 선택하고 K+2번째 회의를 선택하는 경우와 K번째 회의를 선택하지 않고 K+1번째 회의를 선택하는 경우 import sys sys.setrecursionlimit(10**9) N = int(sys.stdin...
www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제풀이: dp를 어떻게 짜야 할 지 생각해내는 것이 어려웠다. 최솟값을 더하는 방법으로 하자니 동일한 비용이 나오는 경우를 고려하는 것이 어려웠고.. 그래서 각각의 경우를 모두 구하는 것이구나 하는 걸 깨달았다..(사실 힌트를 좀 받았다..) 그걸 깨닫고 나니 푸는 것은 간단했다. import sys N = int(sys.stdin.readline()) cost = [] for _ in ..
www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제풀이: dp[0] = [1,0] dp[1] = [0,1] dp[i][0] = dp[i-1][0] + dp[i-2][0] dp[i][1] = dp[i-1][1] + dp[i-2][1] 이미 구해놓은 수열은 반복하여 구하지 않고 바로 출력할 수 있도록 idx를 매번 업데이트 해주었다. import sys T = int(sys.stdin.readline()) dp = [[0,0] for _ in range(41)] dp[0] = [1,0] dp[1] = [0,1] idx = 2 for _ in range(T)..
www.acmicpc.net/problem/13301 13301번: 타일 장식물 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개 www.acmicpc.net 문제풀이: 기본적인 dp 활용 문제인 것 같다. dp[1] = 1, dp[2] = 1로 초기화하고 (편하게 하기 위해 인덱스를 1부터 시작했다.) dp[i] = dp[i-1] + dp[i-2]로 구했다. dp를 구하면서 동시에 둘레의 길이도 구했다. import sys N = int(sys.stdin.readline()) dp = [0]*81 length = [0]*81 dp[1] = 1 dp[2] = 1 len..
www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 문제풀이: set을 이용하여 중복된 수를 제거한 후, 오름차순으로 정렬하였다. 그리고 처음에 주어진 배열의 원소를 새로 정렬한 배열에서 찾고 그 인덱스를 정답 배열에 추가하였다. pypy로 통과하였다. import sys N = int(sys.stdin.readline()) X = list(map(int, sys.stdin.readline().split())) ..
