Hoon222y

https://www.acmicpc.net/problem/14501 예전에 모 기업 문제라고 올라왔던 문제이다. 그냥 간단한 DP인데 멍청하게도 갱신되는 구간을 전부다 확인하지 않는 삽질을 많이 했다. 점화식은 30~36을 참고하면 될것이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #include #include #include #include #include #include #include #include #define MAX_N 10000typedef long long ll; using namespace std; int n,arr[3][111],dp[111]; int main(){..

https://www.acmicpc.net/problem/4196 처음 문제를 풀때는 SCC가 뭔지도 모르고 문제를 풀었었다. 단방향인걸 모르고 양방향이라고 생각하고 Union-find했다가 광탈 해당 문제의 경우 SCC를 만들어 주고 해당 SCC로 묶은 그룹내로 들어오는 간선의 개수가 0인 경우를 세주면 되는 문제이다. 솔직히 SCC를 알았어도 삽질+못풀었을수도 있을꺼 같다. (for문에서 i대신 j 써서 진짜 개삽질 한건 ... 근데 웃긴건 앵간한 예제가 다 나왔었다 ㅋㅋ... ) 일단 문제의 경우 코사라주 알고리즘을 통해 각각 SCC를 만들어 주고 해당 정점이 어떤 SCC 그룹에 속하는지 기록해 둔다. 그 이후 모든 SCC 그룹에서 다른 그룹으로 가는 간선의 경우를 세주면 되는 문제이다. 12345..

https://www.acmicpc.net/problem/2150 SCC문제이다. SCC를 몰라서 이문제 원래는 풀생각이 없었는데 https://www.acmicpc.net/problem/4196 이 문제 단방향인줄 모르고 Union-find 쓰다가 개털려서 공부하고 풀게되었다. 문제는 그냥 SCC를 구현하는 단순한 문제라고 볼수 있다. SCC 관련 포스팅은 추후에 하도록 하겠다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596..

https://www.acmicpc.net/problem/1459 단순하게 생각해서 풀면된다. 주의해야 할 점은 대각선을 이용해서 갈때 더 가까워지는 지점이 있다는 점과 ... 자료형 int범위 벗어난다는 것이다 ; 12345678910111213141516171819202122232425262728#include #include #include #include #include #include #include #include typedef long long ll; using namespace std; ll x,y,c,d; int main(){ cin >>x >> y>>c >>d; if(x>y) swap(x, y); ll ans = min((x+y)*c , x*d+(y-x)*c); if((y-x)%2 ==..

https://www.acmicpc.net/problem/2553 추석인데 할게 없어서 쓸데없이 쓸데없는 문제들만 주구장창 풀고 있는것 같다 ;; 해당문제의 경우 그냥 뒷자리중 0이 아닌 숫자를 찾는 문제인데 그냥 단순 연산을 통해서 계산을 처음 해보았는데 n의 최대크기인 20000을 넣으니까 연산이 한 세월 걸리더라.. 그래서 연산을 좀 줄여보고자 ans의 범위가 10000을 넘어가면 %1000 을 통해 뒤에 3자리만 유지하였더니 통과하였다. 직관적으로 넣고 직관적으로 맞은거라서 %1000에 대해서 왜 1000을 넣었는지는 정당하게 증명은 안된당 ㅎㅎ 12345678910111213141516171819202122232425262728#include #include #include #include #i..

https://www.acmicpc.net/problem/9663 백트레깅 너무 어렵당. 백트레킹과 완전탐색의 차이라고 한다면 alpha beta pruning 처럼 백트레킹에는 커팅되는 과정이 추가된다고 생각할수 있을꺼 같다 (뇌피셜 ) 모든 경우를 다해보지 않고 일단 각 행에는 1개씩은 queen이 존재할 수 있으므로 모든행까지 다 가는 경우는 완성할 수 있는 경우의 수가 +1이 된다. 각각의 배열 3개를 통해서 해당 퀸이 같은 열이 있는지, 같은 대각선 1,2에 있는지를 상수시간에 확인할 수 있다. 어렵당 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include #includ..

https://www.acmicpc.net/problem/11051 무작정 하면 자료형 범위를 벗어난다. 따라서 파스칼의 삼각형 공식을 사용하여 문제를 해결하게 된다.nCr = n-1Cr + n-1Cr-1 을 사용하면 된다. 12345678910111213141516171819202122232425262728293031#include #include #include #include #include #include #include typedef long long ll; using namespace std; int n,k,dp[1111][1111]; int solve(int a,int b){ if(dp[a][b] >0){ return dp[a][b]; } if(a == b || b == 0){ return ..

https://www.acmicpc.net/problem/1759 대표적인 백트레킹(backtracking) 문제라고 볼 수 있다. 해당 문제의 경우 solve의 인자로 현재 위치 , 지금까지 저장 된 str 배열을 사용하였다. https://www.acmicpc.net/problem/2661 해당 문제 또한 추천하는 문제라고 하니 풀어보도록 하자. 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include #include #include #include #include typedef long long ll; using namespace std; int n,m;char arr[111];..

https://www.acmicpc.net/problem/2449 "전구!" 다양한 색깔로 전구가 켜져있고, 인접한 색깔의 경우 바뀔때 동시에 바뀐다고 하면 최소한으로 바꾸는 횟수를 정하는 문제이다.DP로 접근하되, 주의할점은 각자가 색깔을 가지고 있다는 점이다. 27번째 줄을 보면 arr[s],arr[i+1]의 값을 비교하는것을 볼 수 있다. 이는 기준을(전구색이 바뀌는 기준을 왼쪽으로) 잡고 그 색깔이 비교해서 같으면 0을 더하고 다르면 1을 더해주는 문제이다. DP문제의 경우 테이블만 정의 잘하면 되는데 언제쯤에 자연스럽게 되련지... 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #inc..

https://www.acmicpc.net/problem/2098TSP 문제로 유명한 외판원순회 문제이다. 해당문제의 경우 n의 범위가 16까지이기 때문에 일반적인 비트배열만 이용하는것이 아니라 비트마스트+DP를 사용하는 문제이다. 문제를 해결할 때 상태를 보고 지금까지 모든 부분을 다 여행한 경우 (1