BOJ
-
백준(BOJ) 2169번 로봇 조종하기알고리즘 풀이/백준(Boj) 2019. 10. 27. 00:37
문제 : https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 풀이 : 로봇은 왼쪽으로도 갈 수 있기 때문에 일반적인 메모이제이션 cache [y][x]는 최적의 값을 찾아주지 못한다. 따라서 cache 는 3가지 방향을 전부 다 잡아주어야 한다. 코드 ( C++ )
-
백준(BOJ) 2151번 거울 설치알고리즘 풀이/백준(Boj) 2019. 10. 22. 02:22
문제 : https://www.acmicpc.net/problem/2151 2151번: 거울 설치 첫째 줄에 집의 크기 N (1 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 이 곳을 통과한다. ‘!’은 거울을 설치할 수 있는 위치를 나타내고, ‘*’은 빛이 통과할 수 없는 벽을 나타낸다. www.acmicpc.net 풀이 : #와 !을 정점으로 하고 상하좌우로 거울이나 문이 만날수 있다면 간선을 이어주자. 그 후 처음 #에서 마지막 #으로 가는 최단거리 d를 구하자. 이는 BFS를 이용해서 풀어주자. ex) 예제 코드 ( C++ )
-
백준(BOJ) 2422번 한윤정이 이탈리아에 가서 아이스크림을 사먹는데알고리즘 풀이/백준(Boj) 2019. 10. 18. 15:24
문제 : https://www.acmicpc.net/problem/2422 2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 문제 한윤정과 친구들은 이탈리아로 방학 여행을 갔다. 이탈리아는 덥다. 윤정이와 친구들은 아이스크림을 사먹기로 했다. 아이스크림 가게에는 N종류의 아이스크림이 있다. 모든 아이스크림은 1부터 N까지 번호가 매겨져있다. 어떤 종류의 아이스크림을 함께먹으면, 맛이 아주 형편없어진다. 따라서 윤정이는 이러한 경우를 피하면서 아이스크림을 3가지 선택하려고 한다. 이때, 선택하는 방법이 몇 가지인지 구하려고 한다. 입력 첫째 줄에 정수 N과 M이 주어진다. N은 www.acmicpc.net 풀이 : 아이스크림의 선택은 3가지 이니 200 * 200 * 200 총 800만 가지의 경..
-
백준(BOJ) 4연산알고리즘 풀이/백준(Boj) 2019. 10. 16. 02:04
문제 : https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아스키 코드 순서는 '*', '+', '-', '/' 이다. www.acmicpc.net 풀이 : t가 10억이지만 n은 2*n 의 형태나 n^2 의 형태이기 때문에 탐색하는 n의 수는 많지 않고 BFS로 접근할 수 있다. queue q를 생성한후에 * + - / 각각의 순서대로 결과값과 그때의 붙는 부등호의 값을 큐에 넣는다. 조건은 10억이하일 경우 q에 넣어야 하고 나눌때에 n은 0이여서는 안된다. 또 같은..
-
백준(BOJ) 9944번 NxM 보드 완주하기알고리즘 풀이/백준(Boj) 2019. 10. 13. 18:14
문제 : https://www.acmicpc.net/problem/9944 9944번: NxM 보드 완주하기 문제 N×M 보드 위에서 할 수 있는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나누어져 있다. 보드의 각 칸은 빈 칸 또는 장애물이다. 장애물은 아래 그림에선 어두운 사각형으로 표시되어져 있다. 게임을 시작하려면 보드의 빈 칸 위에 공을 하나 놓아야 한다. 아래 그림에서 공은 회색 점으로 표시되어져 있다. 게임은 단계로 이루어져 있고, 각 단계는 아래와 같이 구성되어져 있다. 위, 아래, 오른쪽, 왼쪽 중 방향 하나를 고른 다음, 그 방향으로 www.acmicpc.net 풀이 : 완전 탐색을 이용하여 각 공이 될수 있는 지점마다 재귀호출을 통해 구하자. 선택된 각 지점에서는 상하좌우 ..
-
백준(BOJ) 12996번 Acka알고리즘 풀이/백준(Boj) 2019. 10. 13. 02:11
문제 : https://www.acmicpc.net/problem/12996 12996번: Acka 첫째 줄에 앨범에 포함된 곡의 개수 S와 dotorya, kesakiyo, hongjun7이 불러야 하는 곡의 수가 주어진다. (1 ≤ S ≤ 50, 1 ≤ dotorya, kesakiyo, hongjun7 ≤ S) www.acmicpc.net 풀이 : 한 앨범당 가질수 있는 경우의 수는 7가지 이다 ( a만 b만 c만 a,b만 a,c만 b,c만 a,b,c ) 따라서 각각의 경우의 수를 모두 재귀호출 해준 후 중복은 메모이제이션으로 없애자. 코드 ( C++ )
-
백준(BOJ) 15562 톱니바퀴(2)알고리즘 풀이/백준(Boj) 2019. 10. 10. 13:22
문제 : https://www.acmicpc.net/problem/15662 15662번: 톱니바퀴 (2) 총 8개의 톱니를 가지고 있는 톱니바퀴 T개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, ..., 가장 오른쪽 톱니바퀴는 T번이다. 아래 그림은 T가 4인 경우이다. 이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다 www.acmicpc.net 풀이 : 한번 돌릴때의 일어나는 모든 상호작용은 큐로 처리한다. 즉 어떤 한 시계의 방향을 돌렸을때의 양옆의 톱니바퀴..
-
백준(BOJ) 2234번 성곽알고리즘 풀이/백준(Boj) 2019. 10. 5. 03:38
문제 : https://www.acmicpc.net/problem/2234 2234번: 성곽 문제 대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로그램을 작성하시오. 이 성에 있는 방의 개수 가장 넓은 방의 넓이 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기 위의 예에서는 방은 5개고, 가장 큰 방은 9개의 칸으로 이루어져 있으며, 위의 그림에서 화살표가 가리키는 벽을 제거하면 16인 크기의 방을 얻을 www.acmicpc.net 풀이 : 1번은 bfs를 돌때마다 num을 ++ 해주어서 구한다. 2번은 bfs를 돌며 q에 담긴 횟수를 반환하여 넓이 중 최대 값을..