Hoon222y

https://www.acmicpc.net/problem/1495 DP문제이다. DP[i][j] 정의를 " i번째까지 사용하였을 때 j값을 만들수 있는가 없는가?" 로 정의하였다. 문제의 조건에 따라서 state값의 범위를 0이상 , m이하로 정의를 하고 pos가 n+1 까지 갔을때 state을 가지고 최대값을 가져왔다. 이번에도 재귀로 구현하였다. 근데 재귀 부분에서 ret = max(...) 이 부분 뭔가 깔끔하지가 않은데 이거 어케 해야될지 모르겠당 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include #include #include #include #inc..

https://www.acmicpc.net/problem/5557 DP문제이다. DP[i][j] 테이블 정의를 i번째 숫자까지 사용하였을 때 j가 나오는 경우의 수로 정의하면 dp[i][j] = dp[i-1][j-arr[i]]+dp[i-1][j+arr[i] 가 된다. 물론 조건인 0이상 20 이하를 if문으로 체크해주어야 한다. 27번째 줄처럼 가장 첫수의 가능 경우를 1로 설정해주어야 한다. 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include #include #include #include #include #include #include #define MAX_N 50#defin..

https://www.acmicpc.net/problem/1126 DP문제이다. 해당 문제의 경우 가능한 연산이 총 3가지이다.(1) 첫번째 블럭에 넣기 (큰쪽에 둔다는 의미)(2) 두번째 블럭에 넣기(3) 그냥 버리기 이 3가지 연산을 수행하게 되는데 두 블럭의 높이 차이를 기록하고 그 중 높은쪽을 생각하게 된다. 만약 n번째까지 다 쌓았을때 그 둘의 차이가 0이 되게 되면 두 블럭의 높이가 같다고 볼 수 있다. 문제의 조건에서 모든 블럭의 합이 50만을 넘지 않는다고 하였기 때문에 dp배열은 n*250000으로 생각할 수 있다. (3)번 연산은 36번째 줄 , (1)번 연산은 37번째 줄 , (2)번이 문제인데 만약 두려는 블럭의 크기가 두 블럭 사이의 높이 차 이상,이하일 때를 나누어서 생각해 볼 ..

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 ..