전체 글 (346) 썸네일형 리스트형 백준 1328 - 고층 빌딩 www.acmicpc.net/problem/1328 아이디어 빌딩을 큰 것부터 놓는다고 해보자. 그러면 그 다음 빌딩을 놓는 경우는 크게 세가지로 나눌 수 있다. 1. 가장 왼쪽에 배치 2. 가장 오른쪽에 배치 3. 가운데 아무데나 배치 왼쪽에 놓을 경우 그저 왼쪽에서 볼 수 있는 빌딩의 수가 하나 늘어나는 것이므로 빌딩을 n개 놓을 때 왼쪽에서 l개 보고 오른쪽에서 r개 보는 경우 = 빌딩을 n - 1개 놓을 때 왼쪽에서 l - 1개 보고 오른쪽에서 r개 보는 경우가 성립함을 알 수 있다. 오른쪽도 마찬가지다. 중간에 배치하는 경우는 배치할 빌딩이 가장 작으므로 왼쪽이나 오른쪽에서 볼 수 있는 빌딩의 개수는 변하지 않는다. 즉 빌딩을 n개 놓을 때 왼쪽에서 l개 보고 오른쪽에서 r개 보는 경우 = 빌딩.. [KOI] 백준 2485 - 가로수 icpc.me/2485 예제 tc를 잘 보면 각 가로수 사이의 간격은 최소 공약수가 돼야 함을 알 수 있다. 주어진 가로수들의 간격에서 최대공약수를 구하고 각 가로수의 거리가 최대공약수를 만족하도록 추가할 가로수를 결정하면 된다. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include using namespace std; using ll = long long; ll res = 0; int gcd(int n, int m) { return !m ? n : gcd(m, n % m); } int main() { ios::sync_with_stdio(false); .. [COCI] 백준 9935 - 문자열 폭발 icpc.me/9935 받은 문자열 s를 반복문을 통해 스트링 a에 한글자씩 넣어주자. a에 넣은 마지막 글자가 터트려야 할 문자열 b의 마지막 문자와 일치하는지 확인한다. 일치하지 않는다면 반복문을 계속하면 되고, 일치한다면 a의 마지막부터 검색하여 a의 끝부분이 b와 일치하는지 확인한다. 만약 문자열이 일치한다면 그만큼 터트리고 반복문을 진행시키면 된다. 이 과정을 반복해서 나온 a가 답이 된다. a의 길이가 0이면 FRULA를 출력해주자. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include.. [KOI] 백준 1983 - 숫자 박스 icpc.me/1983 관찰 주어진 숫자 박스에서 숫자를 옮기는 것을 시뮬레이션하면 원하는 답을 구할 수 없을 것이다. 각 숫자의 위치는 순서를 바꾸지 않는 범위에서 자유롭게 옮길 수 있다는 점에 주목해보자. 그렇다면 숫자들이 모두 한쪽에 치우친 상태이고, 상황에 따라 빈칸을 적절히 남겨두는 방식으로 숫자 박스의 값을 최대화시킬 수 있을 것이다. 점화식 이 아이디어를 통해 문제를 해결하고자 한다면 다음과 같은 테이블을 생각할 수 있을 것이다. dp[i][j][k] := i번째 열까지 첫 번째 행에서 빈칸 0을 포함한 j개의 숫자, 두 번째 행에서 빈칸 0을 포함한 k개의 숫자를 사용했을 때 숫자 박스의 최댓값 N은 400이하이므로 400 * 400 * 400 * 4(byte) = 256mb가 나와 문제의.. 백준 2176 - 합리적인 이동경로 www.acmicpc.net/problem/2176 솔루션 1. 더보기 모든 정점 사이의 최단 경로를 구한 다음 그래프 DP를 수행하면서 "합리적인 이동경로"를 탐색하면 간단하게 AC를 받을 수 있다. 전체 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 #include using namespace std; usi.. 이전 1 ··· 57 58 59 60 61 62 63 ··· 70 다음
