https://www.acmicpc.net/problem/1446문제조건D킬로미터의 고속도로 길이 주어진다.지름길의 시작위치, 도착위치, 지름길의 길이가 주어진다.고속도로 끝지점까지 가는 최소거리를 구해라.접근방법 Brute Force로 봐야하나,,? 평소에 잘 접하지 않은 유형의 문제여서 당황스러웠다.최단거리를 구한다고 하면 다익스트라가 떠올랐지만 어떻게 적용시키지,,,? 계속 생각이 안나서 검색의 힘을 조금 빌렸다.  Dijkstra 최단경로를 구하는 대표적인 알고리즘이다.이중 for문을 이용한것과, priority_queue를 이용해서 구현을 선택할 수 있는데, 우선순위 큐가 시간복잡도가 훨씬 작으므로 우선순위 큐를 사용한다.알고리즘의 동작과정은 이와같다.방문하지 않은 노드 중에서 최단거리가 가장 ..

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 문제조건 n x n 크기의 대나무숲 어디든지 판다를 풀어놓을수 있다. 판다는 대나무를 다먹으면 상, 하, 좌, 우 중 한지역으로 이동한다. 이동하는 칸의 대나무가 원래있던 칸의 대나무 수보다 많아야 이동한다. 가장 많이 이동하는 경우의 이동수는? 접근방법 문제를 보자마자 생각이 들었다. '아 그냥 완전탐색돌려서 최댓값 갱신해서 찾자' 내가 좋아하는 DFS 알고리즘으로 모든 경우의 수를 ..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제조건 퇴사 전까지 상담을해서 얻을수 있는 최대 수익을 구하라 단순히 구현 + dp 문제였다. dp[i] : i일까지의 상담중에서 최대 수익 값 완전탐색을 진행하면서 상담에 걸리는 일수가 퇴사 전일때, 구하고자 하는 일자의 수익과, 지금까지의 수익 + 구하고자 하는 일자까지 상담하는 수익을 비교해서 최댓값을 갱신시켜줬다. 소스코드 #include #include using namespace std; int n, t[16], p[16], dp[16]; int main(){ cin >> n; for (int i = 0; i < n; i..

https://www.acmicpc.net/problem/2228 2228번: 구간 나누기 N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되 www.acmicpc.net 문제조건 각 구간은 한개이상의 연속된 수로 이뤄짐 서로다른 두 구간은 겹쳐있거나, 인접하면 안됨 정확히 M개의 구간이어야함 뭔가 좀처럼 접근방법이 떠오르지 않았다. 계속해서 경우의수가 다르기 때문에 DFS로 완전탐색을 돌려야하나 ,,? 어떻게 풀지 감이안와서 접근 방법만 찾아봤다. 역시 dynamic programming,,, 왠지 감이 안잡힌다 생각했다. 식을 세워야하는..

https://www.acmicpc.net/problem/1415 1415번: 사탕 첫째 줄에 슈퍼에 있는 사탕의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 사탕의 가격이 주어진다. 사탕의 가격은 10,000보다 작거나 같은 음이 아닌 정수 www.acmicpc.net 문제조건 사탕의 개수 : n개 사탕 가격의 합이 소수 모양이 똑같은 방법은 사지 않는다. 제일 먼저 떠오른 생각은 집합이었다. 집합이 한번 나오면 모양이 똑같은 방법을 커버할 수 있고, 그 집합의 원소들의 합이 소수가 되면 되기 때문이다. 라고 생각했지만 도저히 이 방법으로는 풀리지 않을 것 같았다,,, 일단 로직에 대해서는 더 고민해보기로 하고 소수 구하는 알고리즘을 보겠다. void isP..