순간을 성실히, 화려함보단 꾸준함을

www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 문제 : 방문할 수 없는 정점들과 방문할 수 있는 정점들이 주어지고 0번 정점부터 n-1번 정점까지 최단거리를 구하시오 해설 : 평범한 다익스트라 문제입니다. 다만 방문 할 수 없는 정점을 뽑았을때는 그냥 무시해주면 되겠죠. 요새 자바 공부를 하고 있어서 자바로 한번 풀어봤는데 문법적인 요소가 꽤 까다로워서 싫네요;;; import java.io.*; import java.util.*..

www.acmicpc.net/problem/11084 11084번: 나이트의 염탐 Cube World와 Baekjoon World가 한창 전쟁 중일 때 있었던 일입니다. 이 두 나라는 r행 c열의 체스판으로 생각할 수 있고, Cube World의 수도는 (1,1)에, Baekjoon World의 수도는 (r,c)에 있습니다. Cube World에서 Baek www.acmicpc.net 문제 : 나이트가 움직일 수 있는 동작이 주어지고 (1,1) 에서 (r,c)까지 최단거리로 갈 수 있는 경우의 수를 구하시오 해설 : 아 이거 문제 잘못읽어서 엄청 해맸습니다. 1e9+9 로 나머지를 구해야 되는데 자꾸 1e9로 해가지고 ㅡ,ㅡ....;; 어쨋든 해설을 하자면 평범하게 dp + bfs 입니다. 이동한 거리는..

www.acmicpc.net/problem/20164 20164번: 홀수 홀릭 호석 호석이는 짝수랑 홀수 중에서 이니셜이 같은 홀수를 더 좋아한다. 운전을 하던 호석이는 앞차의 번호판이 홀수로 가득할 때 사랑스러움을 느낄 정도이다. 전화번호도 홀수만 있고 싶다. 그렇게 www.acmicpc.net 문제 : 규칙에 따라 나오는 수의 홀수의 개수를 세어주면 됩니다. 최소값과 최대값을 구해라 해설 : n이 최대 1e9-1 이므로 아무리 커봤자 9자리를 넘어가지 않습니다. 그래서 전 편하게 문자열을 사용했습니다. 1)0~i 까지 2)i~j 까지 3)j~끝 까지 이렇게 for문 3개를 돌려서 나누어주고 문자열의 길이가 2일때 1일때를 케이스로 또 나누어주면 됩니다. 문자열을 자르기 위해 substr 함수를 사용해..

www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 문제 : 수들이 주어지고 사이에 +,- 만 넣어서 맨 마지막 수를 만들 수 있는 경우의 수를 구하시오 해설 : 점화식만 잘 짤수 있으면 쉽게 풀 수 있는 문제입니다. 매번 나오는 중복된 수들을 일일이 세는 것이 아닌 메모를 해둔다면 빠른시간안에 해결 할 수 있겠죠. dp[i][j] = 이전 단계까지 연산된 결과값에 j번째 수를 +,- 했을때 i 가 나올 수 있는 경우의 수 #include using na..

www.acmicpc.net/problem/2806 2806번: DNA 발견 국내 생물학자들은 기존에 보지 못했던 신기한 DNA 분자를 발견했다. 이 분자는 A와 B로만 이루어진 N글자로 나타낼 수 있다. 이 분자는 계속해서 돌연변이를 한 다음에, A로만 된 분자로 변한다. www.acmicpc.net 문제 : 2가지의 돌연변이가 존재합니다. 1번은 현재 글자만 바꿀 수 있고 2번은 첫문자부터 k 번 문자까지 전부 다른 문자로 뒤집을 수 있습니다. 해설 : 뭔가 문제가 너무 '그럴듯'하게 보였어요. 무슨 뜻이냐면 그냥 현재 당장 최선의 선택을 하면 답이 나올 것이라고 생각했습니다. 한마디로 '그리디'하게 말이죠. 그런데 잘못 생각했더라구요.....증명은 하지 못했으니 그리디 하게 풀지는 못했으니 이건 넘..

www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net 문제 : n개의 정점과 m개의 간선이 주어집니다. 이때 2개의 정점을 선택하는데 모든 정점에서 선택한 2개의 정점 중 가까운 정점과의 거리가 최소가 되게끔 만드시오 해설 : n이 최대 100밖에 안된다는 것은 별짓거리를 다해도 된다는 뜻이죠. 100C2 로 정점을 선택해서 bfs를 돌려도 되고 플로이드-와샬 알고리즘을 사용해서 구해도 되고 등등 전 맘편하게 플로이드-와샬 알고리즘을..

www.acmicpc.net/problem/1090 1090번: 체커 N개의 체커가 엄청 큰 보드 위에 있다. i번 체커는 (xi, yi)에 있다. 같은 칸에 여러 체커가 있을 수도 있다. 체커를 한 번 움직이는 것은 그 체커를 위, 왼쪽, 오른쪽, 아래 중의 한 방향으로 한 칸 www.acmicpc.net 문제 : n개의 체커들이 주어지고 이 체커들은 상하좌우 한칸씩 이동이 가능합니다. 이때 k 개의 체커를 선택하고 이 체커들이 한곳에 모이도록 할때, 최소 이동수를 구하시오 해설 : 어렵습니다!! 음,,일단 먼저 '중앙값의 정리' 를 알고 있다고 생각하고 해설을 진행할 테니 꼭 이 개념에 대해 배우고 오세요 (boomrabbit.tistory.com/88) 여기에 정리해놨습니다. 결국 n개의 좌표중에서..

www.acmicpc.net/problem/2375 2375번: 농구 골대 세우기 첫 줄에 농구를 좋아하는 마을의 개수인 n이 주어지고 다음 줄부터 xi yi pi와 같이 한 줄에 농구를 좋아하는 하나의 마을에 대한 정보가 주어진다. ( 1 ≤ n ≤ 100,000, -1,000,000 ≤ xi, yi ≤ 1,000,000, www.acmicpc.net 문제 : 좌표들이 주어지고 주어진 조건이 최소가 되게끔 농구골대를 설치해라 해설 : 이게 왜 골드2인지는 모르겠습니다. 비슷한 문제는 저어어어어 아래있는데 말이죠 ㅎㅎ 일단 모든 좌표들을 전부 비교해서 O(n^2) 의 시간복잡도로 해결하기에는 무리입니다. n의 범위가 십만이니까요. 그럼 다른 방법을 택해야 되는데 사전지식을 하나 배워갑니다.(머릿속에 잘 ..

www.acmicpc.net/problem/2121 2121번: 넷이 놀기 첫 줄에 점들의 개수 N(5 n >> x >> y; v.resize(n); for (int i = 0; i > v[i].first >> v[i].second; s.insert({ v[i].first,v[i].second }); } int a, b; int ans = 0; for (int i = 0; i < n; i++) { a = v[i].first; b = v[i].second; if (s.find({ a + x,b }) == s.end())continue; if (s.find({ a,b + y }) == s.end())continue; if (s.find({ a + x,b + y }) == s.e..

www.acmicpc.net/problem/14919 14919번: 분포표 만들기 0과 1사이의 실수 a1, a2, ..., aN이 입력으로 주어졌다고 하자. 구간 [0,1)을 다음과 같이 m개의 길이 L=1/m인 부분구간으로 나누자. 각 구간은 순서대로 b1, b2, ..., bm이다. b1: 0 ≤ x < L, b2: L ≤ x < 2L, .. www.acmicpc.net 문제 : [0,1) 인 구간에서 m개의 구간으로 나누었을때 각 구간을 [b1,b2] [b2,b3] ..... [b(m-1),b(m)] 이라고 하자. 이때 주어지는 배열에서 각 구간에 포함되어 있는 개수를 구하여라 해설 : 음....너무 까다로운 문제였어요 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ이게 어떻게 실3이냐!!!! 부동소수점의 개념을 알면 맘편히 ..

www.acmicpc.net/problem/11663 11663번: 선분 위의 점 첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 www.acmicpc.net 문제 : 점들이 N개 주어지고 M개의 선분이 주어질때 각 선분들에 점들이 몇개가 포함되어있는지 구하시오 해설 : 각점들마다 일일이 l n >> m; for (int i = 0; i > A[i]; sort(A, A + n); for (int i = 0; i > x >> y; if (y < A[0] || A[n - 1] < x)cout

www.acmicpc.net/problem/11561 11561번: 징검다리 각 테스트 케이스마다 한 줄에 승택이가 밟을 수 있는 최대 징검다리 수를 출력한다. www.acmicpc.net 문제 : 징검다리를 건너기 위해 점프를 하는데 x 칸을 점프했으면 다음에는 x보다 더 큰 칸을 점프해야 합니다. 이때 처음은 몇칸을 뛰던 전혀 상관이 없습니다. 그러나 반드시 N번째 징검다리는 도달해야 합니다. 이때 최대한 징검다리를 많이 건널때 개수를 구하시오 해설 : 먼저 가장 많은 징검다리를 건너기 위해선 어떻게 해야될까요???우린 한번 가정을 해봅시다. 만약 n이 9이고 처음 4칸을 뛰었다고 해봅시다. 그러면 다음에 뛸때는 무조건 4칸보다 더 많이 뛰어야 하고 반드시 9번째 징검다리에 도달을 해야하니 5칸을 뛰..