Hoon222y

https://www.acmicpc.net/problem/1371 그냥 입출력 문제인데 내가 저렇게 EOF쓰는거 잘 못해서 기록용으로 쓴다. 문제풀 때 Xcode로 했는데 문제는 EOF버튼을 안누르고 입력넣은다음 왜 결과 안나오지? 이렇게 삽질하고 있었다가 그냥 냈는데 맞길래 깨달았다;; 12345678910111213141516171819202122232425262728293031323334353637#include #include #include #include #include #include #include #include #include #define MAX_N 100#define INF 1e8#define MOD 1000000007 typedef long long ll;using namespac..

https://www.acmicpc.net/problem/1328 이 또한 DP문제이다. N,L,R 이 주어졌을때 볼수 있는 가지수를 출력하는 문제이다. DP 테이블의 정의는 DP[i][j][k] = 빌딩이 i개 있을때 왼쪽으로 j개, 오른쪽으로 k개 가 보일때의 개수 라고 정의하고 문제를 접근할 수 있다. 해당 문제를 풀때 힌트라고 한다면 문제를 접근할때 2~n까지의 빌딩이 세워져 있다고 가정을 하고 높이 1의 건물을 넣을 수 있는 경우로 문제를 접근하면 좀 더 쉽게 풀 수 있다. 만약 높이기 1인 빌딩이 가장 왼쪽에 배열되게 된다면 dp[i][j][k] +=dp[i-1][j-1][k] 가 될것이고, 가장 오른쪽에 배열된다면 dp[i][j][k] += dp[i-1][j][k-1] 으로 생각할 수 있다...

https://www.acmicpc.net/problem/10220 해당 문제를 풀면서 Self Representing Seq (이하 SRS)에 대해 처음 알게 되었다. SRS의 정의는 A(i) = A가 i번 등장하는 횟수일 때의 수열(0

https://www.acmicpc.net/problem/1011 힌트는 https://www.acmicpc.net/board/view/13747 에 아주 상세히 적혀있다. 주의할 점은 i를 50000까지 했을때 int범위 벗어난다는 것이다. 후 ... (ll)안해서 계속 틀렸다 .. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include #include #include #include #include #include #include #include #include #define MAX_N 11111111#define INF 1e8#define MOD 1000000007 typedef lo..

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