www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net N이 100이하이므로 O(N^3)인 플로이드-와샬 알고리즘을 사용해도 통과가 될 것 같아서 풀어보았다. 1. M개 만큼 a와 b를 입력받고 a와 b사이의 거리를 1로 cost배열에 넣어준다. 2. 플로이드-와샬 알고리즘을 통해 각 건물 사이의 거리를 구해준다. 3. 브루트포스 방식으로 치킨집이 1번,2번일 때 부터 1번,3번 ... N-1번,N번까지일 때 모든 도시에서의 왕복 시간..
www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 이런 유형의 문제를 처음 보면 '이게 왜 BFS문제지?' 라는 의문이 든다. S층에서 G층으로 가는데 U칸 위로가거나 D칸 아래로 가야하므로 1. 처음에 visited[S]를 방문 처리를 해주고 q에 S를 넣는다. 2. q에서 pop한 뒤 x + U에 해당하는 칸에 방문한 적 있는지 확인하고 없으면 버튼을 누른 횟수를 1 증가시킨다. 3. 2번과 마찬가지로 x - D에 해당하는 칸에 방문한 적 있는지 확인하고 없으면 버튼을..
www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 이제는 무난한(?) BFS문제이다. 단지 3차원배열을 사용해 조금 귀찮을 뿐이다. 1. Test Case마다 m(빌딩상태), time(이동시간), visited(방문여부) 배열을 초기화해주고 m을 입력받는다. 2. m을 전체돌면서 'S'가 있는 칸의 좌표를 sz, sx, sy에 저장하고, 'E'가 있는 칸의 좌표를 ez, ex, ey에 저장한다. 3. bfs를 돌리면서 다음 칸으로 갈때마다 시간을 1씩 더해주고 큐에..
www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net import sys from collections import deque input = sys.stdin.readline q = deque() M, N, H = map(int,input().split()) dx, dy, dz = [1,-1,0,0,0,0], [0,0,-1,1,0,0], [0,0,0,0,-1,1] m = [[list(map(int,input().split())) for _ ..
www.acmicpc.net/problem/21316 21316번: 스피카 위 그림은 처녀자리 중 12개의 별을 12개의 선분으로 이어 만든 그림이다. 시은이는 임의로 각 별에 1부터 12까지의 서로 다른 정수 번호를 부여하고, 12개의 정수 쌍으로 각 선분이 어떤 두 별을 www.acmicpc.net # 입력되는 숫자만 다르고 그래프 모양은 같으므로 "Spica가 몇번인지 어떻게 판단할까??" 생각해본 결과 그래프의 정점의 간선의 갯수로 판단을 해보자고 생각했다. 1. 별자리가 그래프라고 생각하고 x, y가 입력되면 서로 연결되있는 것으로 생각했다. dic[x]에 y를 append하는 식으로 x정점과 연결되어있는 정점들을 모두 저장했다. 별자리를 보면 알 수 있듯이 정점과 연결된 간선의 갯수는 모두 1..
www.acmicpc.net/problem/21318 G번: 피아노 체조 피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 N개의 악보를 가지고 있으며, 1번부터 N번까지의 번호로 부른다. 각 악보는 1 이상 109 이하의 정수로 표현되는 난이도를 www.acmicpc.net 단순히 수학문제여서 정석대로 풀었다가 혼쭐난 문제이다. 1. 처음에 그냥 for문으로 hard배열(난이도)를 돌면서 현재 난이도가 다음 난이도보다 높으면 miss에 1을 더해주고 miss를 return 해주는 식으로 풀었다. import sys input = sys.stdin.readline N = int(input()) hard = list(map(int,input().split())) def mistake(x,..
- 유클리드 호제법: 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. - 그냥 쉽게 말해 A = Bq + R이라는 식에서 A와 B의 최대공약수(GCD)는 B와 R의 GCD와 같다는 뜻이다. 이 알고리즘을 사용하면 빠르게 A와 B의 최대공약수를 구할 수 있다. - 증명은 다음 블로..
www.acmicpc.net/problem/18291 18291번: 비요뜨의 징검다리 건너기 강을 건너는 방법은, (1 → 4), (1 → 2 → 4), (1 → 3 → 4), (1 → 2 → 3 → 4)의 4가지이다. www.acmicpc.net 일단 N=1일 때부터 직접 계산해보면서 규칙을 찾아보았다. N=1일 때 1, N=2일 때 1, N=3일 때 2, N=4일 때 4, N=5일 때 8 ... N=1일 경우를 제외하고 2의 (N-2)제곱이 나오는 것을 확인 할 수 있었다. 단순히 print(2**(N-2))를 하면 N의 범위가 최대 10**9이므로 O(10**9)가 되어서 시간초과가 발생한다. 따라서 분할정복을 이용한 거듭제곱을 해서 시간을 줄여야 한다. # 분할정복을 이용한 거듭제곱은 따로 정리해..
모르는 사이에 조금씩 조금씩..
