그냥 블로그

https://www.acmicpc.net/problem/1486[문제 요약]1. 높이 차가 T보다 낮아야 이동 가능2. 높이가 낮거나 같으면 1, 높이가 높으면 (차이)**2 시간이 걸린다. 3. D 시간만큼 돌아다닐 수 있다. 4. 갈 수 있는 가장 높은 곳의 높이는?  [문제 풀이]일단, 문제를 보면 최단 경로임을 알 수 있었다.-> 양방향 그래프 + 목적지 없음 + 4방향 최단 경로 -> 다익스트라 가능한지 생각해보니 가능 -> 다익스트라 갈김. 주의해야 할 거는, 오는 시간과 가는 시간이 다르기 때문에 다익스트라를 두 번 돌려줘야 한다.  (0,0)에서 (5,5)로 갈 때 여러가지 경로로 갈 수 있고 오는 경로와 가는 경로가 달라도 되기 때문. 그래서, visited[25][25][2] 3차원 ..

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net [문제요약] 40 30 30 50이 있을 때, 괄호를 어떻게 잘 쳐주냐의 문제다. (((40+30)+30)+50) 쳐준다 할 때, 괄호 안에서 더해지고 나오는 값을 계속 기록했을 떄 최소가 되는 경우가 뭐냐 [문제 풀이] 처음 방식을 생각할 때 두 가지가 생각났다. 1) 완전 탐색 2) DP 사실, 완전 탐색으로 풀 수 있는 문제는 아니기 때문에 바로 버리고, DP 아니면 다른 방법 있는..

https://www.acmicpc.net/problem/16434 16434번: 드래곤 앤 던전 첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 HATK (1 ≤ HATK ≤ 1,000,000) 가 주어집니다. i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 ti, ai, hi (ti ∈ {1, 2}, 1 www.acmicpc.net [문제 요약] MaxHP : 최대 생명력, 1이상 필수 curHP : 현재 용사 생명력 (최대 MaxHP) ATK : 용사 공격력 1) 방을 한 칸씩 이동하고, 방에는 포션이나 몬스터가 있다. 2) 몬스터의 피가 0이 될 때까지 공격을 주고 받는다. (용사 선공) 2-1) 몬스터 공격력 만큼 용사 생명력을 차감 2-2) 용사 피..

16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net [문제 요악] 1. 0보다 크고 9보다 작은 수와 수식( + - * )이 있다. ( 길이 시간 제한 0.5초 -> 5000만 정도 보면 수식의 최대 길이가 19이고, 그 중 숫자만 뽑아낸다고 했을 떄 최대 10이다. 경우를 따져보면, 내 바로 뒤에 숫자를 그 다음 숫자와 묶을 것이냐?로 분기가 나뉘어 진다. N 번쨰 숫자에 있을 때, N+1 번째 숫자를 그대로 연산할거냐 (N+1과 N+2를 연산) 하고 더할거냐 이런식인데 이렇게 계산하면 2^10 ..

https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 좀 검색해보니까 다른 방식으로 많이 풀었길래 한 번 포스팅 해봅니다 [문제 요약] 3xN의 빈 공간을 (2X1, 1X2) 타일로 채운다. [아이디어 생각 과정] 일단, 문제를 보고 바로 떠오른 세 가지가 있는데 1) DP 문제 2) N이 홀수일 땐 불가능 3) 어떤 칸이든, 1X2 타일이 "반드시" 들어감 그리고 DP 규칙을 찾으려고 연습장에 이리저리 끄적여 보면서 경우의 수를 생각해 봤다. 진짜 이상한 방식도 많이 생각했는데, 결국 예전에 풀었던 2XN 타일링 방식이 생각이 났고, 거기서 추가해보자는 생각..

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net[문제요약] 1~6까지 나열된 수열이 몇개 있다. ex) - 1 4 3 - 6 2 5 4 - 2 3 각 수열에 있는 숫자들의 순서는 지켜져야 한다. 하지만 중간에 다른 숫자가 들어와도 된다. 일렬로. [문제 풀이] 처음에 문제를 읽으면서 1) 완탐은 안됨 2) DFS? 3) Union-find? 이렇게 3가지를 생각했는데... 3번 Union-find는 순서를 정할 수 없기 떄문에..