dp
-
BOJ) 다리 놓기알고리즘/백준 2020. 7. 16. 16:42
다리 놓기 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 풀이 강의 왼쪽과 오른쪽에 다리를 건설하는데, 교차해서 지으면 안되는 조건의 문제다. 왼쪽보다 오른쪽에 다리를 지을 수 있는 포인트가 더 많다. 여기서 Combination 문제라고 생각했다. 하지만, 30이나 되는 수에서 직접 Combiantion을 구할 수 없었기 때문에 수학 공식을 찾아봤다. nCr = n-1Cr-1 + n-1Cr 이라는 공식이 있다는 것을 알았다. 앞으로는 콤비네이션을 이용해 푸는 문제를 만났을 때, 더욱 효율적으로 풀기 위해 ..
-
BOJ) 카드 구매하기알고리즘/백준 2020. 7. 8. 20:07
카드 구매하기 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 갑자기 dp문제를 풀고싶어서 이 문제를 풀었다. 이 문제는 한번에 정답을 맞추지 못했다. 총 세번을 제출했는데, 첫번째는, 에라토스테네스의 체를 이용해서 소수를 판별하는 것처럼, 특정 인덱스 i 에서 n까지 i 씩 증가하면서 초기에 저장된 가격과 i를 여러번 곱한 값 중 더 큰 값을 저장해주었다. for(int i=1; i
-
BOJ) 쉬운 계단 수알고리즘/백준 2020. 7. 6. 18:27
쉬운 계단 수 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 문제 제목은 쉬운 계단 수 인데, 어렵다.. ㅋㅋㅋㅋ DP 문제를 푼지 오래된 것 같아서 DP 문제를 선택해봤다. 우선 2차원 배열을 사이즈에 따라 생성하는 것 까지는 해놓고 생각을 했다. n자리 수 때, 0~9 숫자가 몇 번 쓰이는지 저장을 해야 풀 수 있는 문제인가 생각을 해보았다. 한 20분정도 생각했는데 이 방법은 아니었다. 다른 저장 방법은 없을까 고민했지만 떠오르지 않았다. 위의 생각에 빠져서 해당 숫자에서 -1 , +1 사이에 있어야 하는 것을 간과한 것이다.. 그래서 질문하기 게시판을 참고했다. 코드가 있는 질문들은 과감하게 넘기고 점화식을 물..
-
BOJ) 상자넣기알고리즘/백준 2020. 6. 23. 13:44
상자넣기 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 �� www.acmicpc.net 풀이 일렬로 정렬된 상자들에서 앞의 상자 크기가 뒤에보다 작으면, 뒤에 상자에 넣어 정리하는 문제였다. dp로 푸는게 적합하겠다는 생각을 하고 코드를 작성했다. 박스를 순차적으로 탐색하면서, 이전의 박스들 중 가장 많이 저장된 박스에 담는 dp를 만들었다. 이때, 앞의 상자 크기가 뒤에 상자 크기보다 작아야한다는 조건을 걸어서 저장하면서, 쉽게 답을 구할 수 있었다. 코드 import java.io.BufferedReader; import java.io.I..
-
BOJ) 방법을 출력하지 않는 숫자 맞추기알고리즘/백준 2020. 6. 18. 15:25
방법을 출력하지 않는 숫자 맞추기 13392번: 방법을 출력하지 않는 숫자 맞추기 아래 그림과 같이 N개의 회전이 가능한 숫자 나사가 아래위로 연결되어 있다. 가장 위에 있는 숫자나사는 숫자나사 1이고 가장 아래에 있는 숫자나사는 숫자나사 N이다. 모든 숫자나사는 각각 10� www.acmicpc.net 풀이 매우 어려웠던 문제였다. DP를 이용하는 문제이고, left와 right를 각각 저장하면서 진행해야한다는 것까지는 눈치를 챘다. 하지만, 계속되는 오답과 시간초과에 멘붕이 왔다. 다른 분들의 풀이를 참고하기로 했다. 저장하는 DP를 이동 뿐만 아니라, 큐브의 숫자인 0~9에 대해 저장해주는 것이었다. 이에 대해 이해하기는 했지만, 가까운 미래까지는 이 생각에 도달하지는 못할 것 같았다. 그래서, 이..
-
BOJ) 자동차경주대회알고리즘/백준 2020. 6. 18. 15:05
자동차경주대회 2651번: 자동차경주대회 첫째 줄에 정비소에서 정비하는데 걸리는 총 정비 시간을 출력한다. 둘째 줄에 방문하는 정비소의 개수를 출력한다. 셋째 줄에는 방문하는 정비소의 번호를 한 줄에 차례로 출력하며 정비소 번� www.acmicpc.net 풀이 이 문제는 DP를 활용해서 풀었다. 정비소의 위치와 걸리는 시간을 담을 배열을 각각 선언해서 값을 저장해줬다. 이 때, 출발 지점인 0과 도착 지점인 마지막 위치도 같은 배열에 저장해서 도로의 출발점과 도착점까지 탐색하도록 설정했다. 각 정비소를 들르면서, 이전까지 최대 이동거리인 maxDist안에 있는 정비소를 찾아 걸리는 시간의 최소값을 구했다. 해당 정비소가 최소 시간을 만족하기 때문에, 걸리는 시간을 더해주면서 마지막 도착지점까지 시간이 ..
-
BOJ) 연속합알고리즘/백준 2020. 6. 12. 23:21
연속합 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 오늘 어려운 문제에 여러개 도전하다가 실패해서 그런지 머리가 잘 돌아가지 않았다. 그래서, 예전에 풀었던 기억이 있어서 참고해서 풀었다. 우선, 막혔던 부분은 partialSum을 저장하는 부분이었다. Math.max(0,partialSum)을 통해 해당 번호에서 다시 시작하는게 좋은지, 지금까지 더해왔던 수를 계속 이용하는게 좋은지 판별해주는 부분이 놓친 부분이었다. 이전까지의 합이 양수면, 거기에 더해주는게 더 합리적이기 때문에.. 또한, 0과 비교하는 이..
-
프로그래머스 Lv.3) 정수 삼각형 (DP)알고리즘/프로그래머스 고득점 Kit 2020. 6. 4. 16:33
정수 삼각형 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 풀이 DP를 푸는 방법 중 두 번 모두 bottom-up 방식으로 문제를 풀었다. 문제의 조건은, 삼각형 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 최대 값이 되는 것이다. 그래서 첫번째 풀었을 때는, 다른 분의 풀이를 보고 이해했던 것 같다. 첫번째 푼 방식은 위의 두 경로 중 최대 값을 같는 경로로 탐색하면서 마지막에 도착한 다음, 정렬을 통해 가장 큰 값을 리턴해주었다. 두번째 푼 방식은, 이 경우, out of idx 방지를 신경써주지 않아도 되고, sort를 따로 해주지 않아도 된다는 생각에서 풀이 ..