DP
-
[프로그래머스] 스티커 모으기(2)문제 풀이 2020. 10. 2. 17:56
스티커 모으기(2) 문제) https://programmers.co.kr/learn/courses/30/lessons/12971 풀이)dp를 이용해서 풀어야 하는 문제다 점화식dp[i] = i번째 스티커를 뗄 경우, 지금까지 얻을 수 있었던 점수의 최대값 dp[i] = max(dp[i-2] + sticker[i], dp[i-1]) //i번째 스티커를 뗄 경우, i-2번째 스티커를 뜯어낸 후 합쳐왔던 점수에 i번째 스티커 점수 합침 i번째 스티커를 떼지 않을 경우, i-1번째 스티커를 뜯어낸 후 합쳐왔던 점수 가져옴 * 주의점 *원형으로 연결되어 있기에, 첫번째 스티커를 뜯어낼 경우 마지막 스티커를 뜯지 못한다.이를 위해 첫번째 스티커를 뜯었을 경우와 아닐 경우를 나눠서 계산해본다. 코드)include #..
-
[프로그래머스] 경주로 건설문제 풀이 2020. 9. 25. 18:01
경주로 건설 문제) https://programmers.co.kr/learn/courses/30/lessons/67259 풀이)헤매다가 질문글을 보고 오류를 찾은 문제이다. 참고 질문글) https://programmers.co.kr/questions/12180 PQ와 DP를 이용하고, 새로운 비용이 작거나 같을 경우만 무조건 업데이트 시키면서 이동가능하게 했었는데이동 방향에 따라 비용의 대소가 역전되는 경우가 있었다. 그래서 DP를 이용할 때 방향까지 저장해서 풀었다. int dp[i][j][k] = (i,j)위치에 k방향으로 도달했을 때까지 든 최소 비용 과정1. 비용을 Memoization할 배열을 모두 나올 수 없는 최대 비용으로 초기화.( INF = 987654321 )2. 처음 출발할 칸 즉,..
-
[프로그래머스] 단어 퍼즐문제 풀이 2020. 9. 23. 17:25
단어 퍼즐 문제) https://programmers.co.kr/learn/courses/30/lessons/12983 풀이)처음에 BFS를 이용해서 풀었으나 효율성을 통과하지 못했다. 효율성 통과 x 코드) 12345678910111213141516171819202122232425262728293031323334353637383940414243#include #include #include #include #include using namespace std; bool cmp(const string &a, const string &b) { return a.length() > b.length();} int solution(vector strs, string t){ int answer = 0; sort(st..
-
[백준] 4013번 ATM문제 풀이 2020. 9. 5. 19:32
4013 ATM 문제) https://www.acmicpc.net/problem/4013 풀이)SCC, dp를 이용해서 푸는 어려웠던 문제였다. 같은 간선을 여러번 사용할 수 있기 때문에,임의의 정점을 방문한다고 할때 그 정점이 속한 SCC내의 모든 정점을 방문해서 최대 현금을 구한다. 과정1. kosaraju algorithm을 이용해 SCC을 구한다. SCC를 구할때, 각 정점이 어떤 SCC에 속하는지 표시해준다 //int node[i] => i 번 정점이 속하는 SCC번호 각 정점이 속하는 SCC의 총 현금을 저장해준다 //int scc[i] => i 번 SCC의 총 현금, 즉 SCC에 속한 정점들의 현금 합 SCC 끼리 연결될 수 있다면, 그 연결 간선을 저장해준다 //vector adj_scc[..
-
[백준] 1949번 우수마을문제 풀이 2020. 8. 23. 17:34
1949 우수마을 풀이)백준 2533번 사회망서비스 문제랑 똑같이 dp를 사용해서 풀면 된다.사회망 문제 설명) https://comyoung.tistory.com/41 +)트리는 사이클이 없는 무방향 그래프이므로 어느 정점에서 시작하든 상관없다. 나같은 경우는 1번 마을을 트리의 root라고 생각하고 시작해줬다. 주의사항처음에 트리 구현할 때무조건 번호 작은 노드가 번호가 큰 노드의 부모이게 만들어, 양방향으로 마을을 연결되지 않게 했었다.이렇게 풀면 트리가 제대로 구현되지 않아 틀리게 된다.반례) 1-3, 2-3 코드) 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include us..
-
[백준] 2186번 문자판문제 풀이 2020. 8. 15. 19:12
2186 문자판 문제알파벳 대문자가 한 칸에 한 개씩 적혀있는 N×M 크기의 문자판이 있다. 편의상 모든 문자는 대문자라 생각하자. 예를 들어 아래와 같은 문자판을 보자KAKTXEASYRWUZBQP 이 문자판의 한 칸(아무 칸이나 상관없음)에서 시작하여 움직이면서, 그 칸에 적혀 있는 문자들을 차례대로 모으면 하나의 단어를 만들 수 있다. 움직일 때는 상하좌우로 K개의 칸까지만 이동할 수 있다. 예를 들어 K=2일 때 아래의 그림의 가운데에서는 'X' 표시된 곳으로 이동할 수 있다. X X XX XX X X 반드시 한 칸 이상 이동을 해야 하고, 같은 자리에 머물러 있을 수 없다. 또, 같은 칸을 여러 번 방문할 수 있다.이와 같은 문자판과 K, 그리고 하나의 영단어가 주어졌을 때, 이와 같은 영단어를 ..
-
[백준] 11060번 점프점프문제 풀이 2020. 7. 22. 17:04
11060 점프점프 문제재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 프로그램을 작성하시오. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다. 입력첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 Ai (0 ≤ Ai ≤ 100)가 주어진다. 출력..
-
[백준] 11048번 이동하기문제 풀이 2020. 7. 11. 18:14
11048 이동하기 문제준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오. 입력첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지..