곧죽어도 콛잉

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제도 앞에서 푼 것과 같은 문제이다. (1,2,3 더하기 4) K라는 가치를 만들기 위해 값들을 더하는 경우의 수를 구하는 것이다!!! 동전은 무한대로 사용할 수 있다는 점을 명시하라! #include using namespace std; int dp[100001], n, k, t; int main(){ cin >> n >> k; dp[0]=1; for(int i = 0 ; i < n ; i+..

https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 오랜만에 올린다 ㅠ 블로그에 글 열심히 써야겠다. DP가 너무 어려워서 천천히 해가는 중이다.. DP는 브루트포스, 백트래킹 안되면 해야하는 친구이다. 이 문제는 3중 for문 돌려서 푸는 문제는 아닌건 알것이다. 그렇다면 어떻게 해결해야할까?? 논리가 생각하기 어렵다,, 바로 해결 방법을 봐보자. 먼저 간단하게 살펴보자면, 최종적인..

https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 이 문제는 그냥 노가다. 이전에 풀었던 톱니바퀴(2)와 같은 문제다. 조금 더 응용된 버전. 일단 주어진 원판들을 2차원 배열로 표현할 수 있다!! 각 원판들의 회전은 독립적이므로 각 원판들의 회전은 rotate()로 쉽게 구현이 가능하다 원판들의 회전은 쉽게 구하지만 "인접" 조건을 구현하는 것이 까다롭다. 나는 정공법으로 제시된 인접 조건을 그대로 구현하는 방향으로 풀었다. ..

https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 이 문제는 이분 탐색인 걸 모르면 어렵다. 우리가 찾아야할 값(블루레이의 최소 크기)을 key로 두고, 이 값을 계속해서 찾아나가는 형식으로 풀어야한다. 자세한 건 코드를 보며 풀어보자! #include using namespace std; int N, M, res=INT_MAX; vector lectures; bool check(int mid){ int num=0; // 필요한 블루레이 수 int nw..

https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 이 문제는 어렵게 접근하면 한도 끝도 없이 어려워진다.. 단순하게 시각화해서 문제를 해결해보자! 우선 도화지에 선분을 그어보자. 최종적으로 겹치는 곳을 제외한 선분의 합만 구하면 끝이다! 즉, 우리가 주목해야할 것은 시작점과 끝점이다. 만약 새로 그은 선분의 시작점(ns)이 원래 그어져있는 시작점(bs)과 끝점(be) 사이에 있고, 새로 그은 선분의 끝점(ne)이 ..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 아이코.. 벽개수를 빼는거를 잊어버렸다 이것때메 개고생했다아.. 벽은 사각지대에 포함하면 안됩니다~~! cctv개수가 8개밖에 안되므로 문제는 진짜 있는 그대로 구현만 해주면 된다. 약간 노가다로 풀어서 좀 화가나긴하는데 그래도 여차저차하면 어떻게든 된다 .. 이건진짜 시간싸움인 문제 같다. 코드 중에 감시(overwatch) 부분 해결하는 방법을 생각하기가 좀 까다로웠다. 그냥 노가다..