이번문제는 다익스트라 문제예요.. 하지만 주어진 두점을 지나야 해요! 제가 생각한 풀이법은 이렇습니다.1. 두 점중에서 시작점과 가까운 거리를 구합니다!2. 두 점중에서 도착점과 가까운 거리를 구합니다!3. 두 점의 거리를 더해줍니다. *그리고 만약 첫번째 점을 시작점과 연결했다면 끝나는 점은 다른 한점과 연결해야 최소비용으로 지나갈 수 있겠죠? 교차해서 지나가야 한번씩 방문하면서 최소비용이 나와요! ->이렇게하면 '시작점 ~ (두 점중 택1) ~ (나머지 점) ~ 도착점'의 최단거리가 나올 것 같아요!그러므로 주어진 두 점에서 다익스트라알고리즘을 돌리면 최단거리가 나오겠죠? 123456789101112131415161718192021222324252627282930313233343536373839404..
https://www.acmicpc.net/problem/11066 dp제는 너무 어려운거 같아요. 바텀업보다 탑다운이 코드짜기 편하고해서 점화식만 잘세우고, 탈출조건만 잘짜면 된다하는데 아직 많이 어렵네요.. 밑에 코드에서는 start~end 까지 보는데 for문을 돌면서 start ~ i의 최소합 i+1 ~ end까지의 최소합을 구해서 리턴하면 되네요. sum배열은 누적합을 저장해놓은 배열이예요. 12345678910111213141516171819202122232425262728293031323334353637383940414243#include #include #include using namespace std; int K;vector file;vector sum;vector dp; unsigne..
https://www.acmicpc.net/problem/1463 백준 1463번 1로 만들기 입니다. 제가 dp를 연습하기 시작했는데, 연습문제로 풀기에 좋은 문제같았습니다.n이 주어지면 그 숫자를 1로 만드는데, -1 , /2, /3 (나누어 떨어진다면) 만큼 이동합니다. 이동할 때 이동횟수 + 1 을 해주는 것이 중요!밑에는 제 코드입니다. 12345678910111213141516171819202122232425#include #include //min함수#include using namespace std; vector dp; int make1(int n) { if (n == 1) return 0;//도착 if (dp[n] != -1) return dp[n];//이미 계산했다면 그 값을 리턴 in..
https://www.acmicpc.net/problem/2573 백준 2573번 빙산입니다. 개인적으로 괜찮게 푼 문제라고 생각하는데.. 다른분들 푼 코드를 보면 뭔가 아쉬운 문제입니다. 이번 문제에서 어려웠던것은 녹을 때 빙산들을 어떻게 처리할 것인가인데요. 저는 따로 지도를 만들어서 그 지도에 그린것들을 다시 복원하는 방법을 선택했어요.밑에는 제 코드입니다.1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798#includ..
https://www.acmicpc.net/problem/2589 이번문제는 보물섬입니다. 문제 풀때 가장 고민했던것은 '시작점을 어떻게 찾을 것인가'였는데요. 답은 가능한 모든 시작점에서 탐색을 하면서 가장 긴 거리를 찾는 것입니다! 나머지는 컴퓨터가 알아서 다해줄겁니다..밑에는 제 코드입니다.1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include #include #include using namespace std; vector map;//지도vector visited;//방문체크typedef p..
https://www.acmicpc.net/problem/5014 이번문제는 전형적인 BFS문제입니다. 시작점부터 목표점까지 갈 수 있도록 탐색하는 문제입니다. 밑에는 제 코드입니다.1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #include using namespace std; int F, S, G, U, D; vector floors;vector visited;//visited에 이동횟수 입력 bool isSafe(int pos) { if (pos F) return false; else return true;//범위 체크} int bfs(int from,int to) { queue q; q..
https://www.acmicpc.net/problem/7576백준 7576번 토마토 문제입니다. 이번문제는 DFS로는 접근하기 어려운 문제인 것 같아요. 혹시 DFS로 푸신분이 있으시다면 댓글로.. 알려주세요! 이번문제도 다른 탐색문제들과 다른것은 많이 없습니다. -1이 탐색 불가능한점(바다문제라면 바다에 해당되겠네요)으로 설정 후 탐색해 주시면 됩니다. 또한 다른 문제들은 시작점이 하나지만 이문제는 시작점이 여러개가 될 수 있는 문제입니다. 따라서 큐에 시작점을 삽입할때 1로 표시된 시작점들을 모두 넣어주어야 해요!! 그럼 컴퓨터가 알아서.. 다해줍니다^^. 밑에는 제 코드입니다.1234567891011121314151617181920212223242526272829303132333435363738..
https://www.acmicpc.net/problem/6593 이번문제는 백준 6593번 상범빌딩 이예요. 제가 요즘 풀고있는 탐색문제들과 같은 종류입니다. 여기서 추가된건 상하좌우에다가 높이까지 추가된 경우인데요, 탐색에서 높이만 추가해서 탐색하면 아주 쉽게 풀 수 있는 문제입니다.밑에는 제 코드입니다.123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293#include #include using namespace std; typedef s..
https://www.acmicpc.net/problem/12851 https://www.acmicpc.net/problem/13549 https://www.acmicpc.net/problem/13913 이전 백준 1697번 문제의 연장선으로 나온 문제입니다. 숨바꼭질2가 제일 어려운거 같고.. 3이 제일 어려웠던 거 같아요.. 4는 어느정도 생각하면 풀리는거 같네요. 코드에 주석으로 설명할게요.밑에는 제 코드입니다. 2020. 2. 12. 수정
https://www.acmicpc.net/problem/1697 백준 9663번 숨바꼭질 문제입니다. 이번 문제도 BFS 알고리즘을 사용해서 풀었어요. DFS로 해결하려면 힘들 것 같아요. 만약 testCase가 50000 1일 경우에 정말 많은 스택공간이 필요하기 때문에 재귀함수는 메모리초과가 날 것 같고, 스택을 이용하면 시간초과가 날것 같기에.. BFS를 활용하는게 좋아보아요. 처음 구현할 때, 1에서 출발하면 *2 나 +1이 중복되서 체크하는 데 문제가 있을거라고 생각했었는데, 어차피 둘다 이동 횟수는 1증가해서 상관 없을 것 같네요..밑에는 제 코드입니다.123456789101112131415161718192021222324252627282930313233343536373839404142#in..