본문 바로가기

전체 글127

백준 16469 소년 점프 C++ 간단한 해설 방문 배열을 3개 만들어서 bfs를 통해 최소 방문을 시간을 기록한다.3개 배열을 비교하고, 그 최대값이  세 악당이 모일 때 걸린 시간이다. 답#include #include #include #include using namespace std;int r,c;int board[100][100];int visited[3][100][100];int dy[4]={0,0,1,-1};int dx[4]={1,-1,0,0};bool set(int index,int y,int x,int val){ if(y=r||x=c) return false; if(board[y][x]==1) return false; if(visited[index][y][x]>r>>c; for(int i=0;i>str; for(int .. 2024. 10. 21.
백준 16562 친구비 C++ 간단한 해설 친구의친구는친구니깝부모의부모는부모이다즉디스조인트셋, union-parent를 사용하자. N이 최대 10000이라서 union by rank를 안해도 된다. 답 #include #include #include using namespace std;int n,m,k;int parent[10001];int findParent(int vertex){ if(parent[vertex]!=vertex) return findParent(parent[vertex]); return parent[vertex];}int main(){ cin.tie(0); ios_base::sync_with_stdio(0); for(int i=1;i>n>>m>>k; vector v(n+1); f.. 2024. 10. 15.
백준 27978 보물 찾기 2 C++ 간단한 해설 그냥 다익스트라를 활용하면 된다.어렵지 않고 그냥 쉽게 풀음   답 #include #include #include #include #include using namespace std;vector> v;vector> visited;int ans=987654321;int dy[8]={1,1,1,0,0,-1,-1,-1};int dx[8]={1,0,-1,-1,1,1,0,-1};int h,w;bool set(int y,int x,int val){ if(y=h||x=w) return false; if(v[y][x]=='#') return false; if(visited[y][x]>h>>w; v.resize(h,vector(w)); pair startPoint; pair endPoint; for(int.. 2024. 10. 10.
백준 10830 행렬 제곱 C++ 간단한 해설 A의 B제곱은 분할정복으로 다음과 같은 공식을 사용할 수 있다.A^B=A^(B/2)*A^(B/2) (B is even)A^B=A^((B-1)/2)*A^((B-1)/2)*A (B is odd) 여기서 B에 해당되는 값들을 잘 생각해보면 1, 2, 2^2, 2^3... 이런식으로 분할할 수 있다. 만약에 B가 5라고 생각해보자 그러면 B=2^2+1이라고 생각할 수 있다.만약, B가 21이라고 생각하면 B=2^4+2^2+1이다. 그러면 A의 2제곱n지수들을 메모이제이션하고, B를 비트마스킹해서 그 값들을 곱하는 방식으로 사용하면 된다. B의 최대치가 100000000000이니까 B=100000000000일때를 생각해보자. B를 이진법으로 변환했을 때, 0000000000000000000000000.. 2024. 10. 6.
백준 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.

티스토리툴바