[백준 / BOJ] 16953 A -> B
문제 출처 : www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 정수 A와 B가 주어진다. A에 *2연산과, A*10+1연산을 할수있을때, A를 B로 바꾸는데 필요한 최소연산횟수를 구하는 문제다. 이때, A를 B로 바꾸지 못한다면, -1을 출력하면 된다. 풀이 전형적인 BFS문제다. BFS알고리즘은 자기와 가까운 위치부터 탐색하기때문에, 항상 최소연산으로 A를 B로 바꿀수있다. A와 B의 범위가 최대 10억이기때문에, check배열로는 같은숫자방문을 체크해줄수없다. 하지만, 연산의 증가폭이 넓기때문에, 모든경우를 다 봐줘도 시간초과가 나지않는다. 예시로, 1. *2 연산은 32번만 반..
[백준 / BOJ] 16724 피리 부는 사나이
문제 출처 : www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net N*M지도가 있고, 그 위에 영과일 회원들이 있다. 지도의 각 칸에는 U,D,L,R 이 쓰여있는데, (순서대로 위, 아래, 왼쪽, 오른쪽) 성우가 피리를 불기 시작하면, 영과일 회원은 자기 발 아래의 방향에 맞게 이동한다. 재훈이는 영과일 회원의 안전을 위해 SAFE ZONE을 설치할려고한다. 영과일 회원이 어디에 있던지 항상 SAFE ZONE으로 들어갈수있도록..
[백준 / BOJ] 2342 Dance Dance Revolution
문제 출처 : www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 승환이는 DDR게임을 할려고한다. 중앙, 위, 왼쪽, 아래, 오른쪽 순서로 0, 1, 2, 3, 4 라고 할때, 승환이가 눌러야할 방향이 순서대로 주어진다. 한 위치에서 다른 위치로 발을 이동시킬때드는 힘의 크기가 다를때, 모든 방향을 누를때 드는 최소힘의 크기를 구하는 문제다. 풀이 BFS나 DP로 풀리는 문제다. 왼쪽발을 움직여서 해당 숫자를 누르는게 당장은 ..