본문 바로가기

알고리즘/백준28

백준 1956 운동 C++ 간단한 해설 v가 적고, 간선 또한 v*(v-1)개이다에서 사실 플로이드를 염두에 두고 있었으나, 다익스트라로 풀리나 한번 해봤다. 결국 33~36%대에서 시간초과가 나서 플로이드로 풀었다.  플로이드를 구현하는 법은 상당히 간단하다. for문을 3번 돌리는데 이런 식으로 생각하면 편하다. for(int k=1;k 답 #include #include #include using namespace std;vector> graph; int ans=987654321;int v,e;int main(){ cin.tie(0); ios_base::sync_with_stdio(0); cin>>v>>e; graph.resize(v+1,vector(v+1,987654321)); int a,b,c; for(int i=0;i>.. 2024. 10. 6.
백준 17069 파이프 옮기기 2 C++ 간단한 해설 단순히 메모이제이션을 통해서 파이프를 옮기면 된다. 파이프의 모양이 3개 있으니까, 2차원 위치를 나타내는 배열 + 파이프의 모양으로 3차원 배열 선언하였다.  그런데 자꾸 예제 5번의 답이 50445956이 나와서, 다른 예제는 다 맞는데 뭐가 문제이지 1시간고민했었는데,정답인 4345413252가 43억으로 int 형의 범위를 초과해서 그런 것이였다. 감이 다죽었네...  답 #include #include #include #define ll long longusing namespace std;int main(){ cin.tie(0); ios_base::sync_with_stdio(0); int n; cin>>n; vector> v(n,vector(n)); .. 2024. 10. 2.
백준 2294 동전 2 C++ 간단한 해설 1차원 dp로 해결 밑이랑 비슷한 방식 백준 1106 호텔 C++2차원 dp로 할려다가, 기존의 배낭문제처럼 최댓값을 이어서 받는 것은 고객 수의 idx가 배수가 아닐 경우, 문제가 생겨서 1차원 dp로 해결하였다. 주석을 상세히 다시 달아보았다. 적어도 c명 이상ash9river.tistory.com    답#include #include #include using namespace std;int main(){ cin.tie(0); ios_base::sync_with_stdio(0); int n,k; cin>>n>>k; vector v(n); for(int i=0;i>v[i]; } sort(v.begin(),v.end()); vector dp(k+1,987654321); for(int i=.. 2024. 9. 30.
백준 14502 연구소 C++ 간단한 해설 그냥 간단한 브루트포스 + bfs10분컷 답#include #include #include #include using namespace std;vector picker;vector> v;vector> canMakeByeok;vector> vir;int n,m,ans;int dy[4]={1,-1,0,0};int dx[4]={0,0,1,-1};bool set(int y,int x,vector>& table){ if(y=n||x=m) return false; if(table[y][x]!=0) return false; return true;}void bfs(){ vector> tmpV=v; for(int i=0;i> q; for(int i=0;i>n>>m; v.resize(n,vector(m)); .. 2024. 9. 26.
백준 17141 연구소 2 c++ 간단한 해설N이 50밖에 안되서 간단하게 바이러스를 놓는 위치를 정하는 것은 브루트 포스, 바이러스 전파를 BFS로 하면 쉽게 풀린다.  답#include #include #include #include #include using namespace std;vector> vir;vector picker;vector> v;int n,m,ans=987654321;int dy[4]={1,-1,0,0};int dx[4]={0,0,1,-1};bool set(int y,int x,vector>& visited){ if(y=n||x=n) return false; if(v[y][x]==1) return false; if(visited[y][x]) return false; return true;}vo.. 2024. 9. 25.
백준 17485 진우의 달 여행 (Large) C++ 간단한 해설단순하게 메모이제이션을 활용하는 dp문제사실 더 최적화 할 수 있지만, 경우의 수가 적어서 그냥 3차원 배열로 관리하였다. 답#include #include #include using namespace std;int main(){ cin.tie(0); ios_base::sync_with_stdio(0); int n,m; cin>>n>>m; vector> v(n,vector(m)); vector>> dp(n+1,vector>(m,vector(3,987654321))); for(int i=0;i>v[i][j]; } } for(int i=0;i 2024. 9. 25.

티스토리툴바