본문 바로가기

알고리즘36

백준 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.
백준 1036 36진수 C++ 간단한 해설36진법의 수 N개가 주어진다. 36진법 숫자(0-9, A-Z) 중에서 K개의 숫자를 고른다. 그러고 나서 N개의 수 모두에서 나타난 그 숫자를 Z로 바꾼다. 여기서 Z로 바꾸는 기준이 (Z - 기존수)의 값이 가장 큰 value를 고르면 된다. 만약 예제가 이렇게 있다고 생각해보자2A0B01 A를 Z로 변환하면 Z0+B0=1A0이 된다.B를 Z로 변환하면 A0+Z0=190이 된다. 그래서 우선순위 큐를 활용하던가, 정렬을 이용해서 (Z-기존수)의 합들의 값이 가장 큰 진수를 고르면 된다. 테이블을 만들어서 해당되는 자리수와 그에 맞는 진수, 이 둘에 대한 개수를 넣으면 좀 더 편하게 생각할 수 있다.  그런데, Z랑 0일 때, 특이 케이스를 배제하지 않으면 5%틀이 계속 나오게 된다... 나.. 2024. 9. 24.

티스토리툴바