C++
-
백준(BOJ) 3085번 사탕 게임알고리즘 풀이/백준(Boj) 2019. 10. 27. 02:05
문제 : https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 문제 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다. 가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다. 사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하 www.acmicpc.net 풀이 : 상하좌우 바꿀 수 있지만 위쪽이나 왼쪽 교환은 이전 칸에 오른쪽이나 아래쪽 교환으로 구할 수 있기 때문에 아래, 오른..
-
백준(BOJ) 1937번 욕심쟁이 판다알고리즘 풀이/백준(Boj) 2019. 10. 27. 01:37
문제 : https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-) 이 www.acmicpc.net 풀이 : 0,0부터 n n까지 모든 경우의 수를 조사하여 최대 길이를 찾아야 한다. 이때 한 y,x에서의 길이는 이미 구해진..
-
백준(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) 14225번 부분수열의 합알고리즘 풀이/백준(Boj) 2019. 10. 25. 02:42
문제 : https://www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 수 있다. 하지만, 4는 만들 수 없기 때문에 정답은 4이다. www.acmicpc.net 풀이 : S의 최대 크기는 20 이고 한 숫자당 10만이하 이니 합에 최대값은 20 * 100000일것이다. 이 배열을 잡은 후에 재귀호출을 통해서 각 부분 수열을 더하거나 지나치거나 하여 모든 경우의 수를 체크해주자. 그 후 1부터 시작해서 값이 false라..
-
백준(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 풀이 : 완전 탐색을 이용하여 각 공이 될수 있는 지점마다 재귀호출을 통해 구하자. 선택된 각 지점에서는 상하좌우 ..