분류 전체보기 (58) 썸네일형 리스트형 SCPC 예선 1차 통과 2솔하고 서브테스크를 하나도 못긁어서 1차도 통과 못할까봐 걱정 많이했는데 다행히 통과했네요. 들리는 소문으로는 120점 정도가 커트라인같습니다. 2라운드부터 요구되는 알고리즘 수준이 높아서 세그먼트 트리나 팬윅트리 같은 문제를 풀어봐야할 것 같습니다. 백준 17398 통신망 분할 http://www.acmicpc.net/problem/17398 17398번: 통신망 분할 첫 번째 줄에는 통신탑의 개수인 자연수 N, 통신탑 사이의 연결의 개수인 자연수 M, 통신망 연결 분할 횟수인 자연수 Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000, 1 ≤ Q www.acmicpc.net 유니온 파인드를 사용하는 문제였습니다. 문제를 푸는 아이디어가 재밌는 문제인데요. 처음에는 단절점, 단절선 문제같아 보였는데 시간복잡도를 보고 다른 아이디어로 푸는걸 깨달았습니다. 문제는 간선을 순서대로 빼고 나눠지는 두 연결요소의 정점 수를 곱하는거지만 거꾸로 생각해보면 문제에서 주어진 순서 반대로 간선을 추가하고 연결되는 두 연결요소의 정점 수를 곱한다고 생각.. 백준 9983 더 푸르게 http://www.acmicpc.net/problem/9983 9983번: 더 푸르게 체스에서 전투를 피하고 기물을 지키려할 때 좋은 전략은 만남을 피하는 것이다. IBM은 Deep Blue에게 체스에서 이런 전략을 학습시키려한다. 따라서 IBM은 서로를 공격하는 기물이 없도록 만들 때, www.acmicpc.net 비트마스킹을 사용해 풀었습니다. O(2^15*100)이므로 브루트포스로 모든 기물이 놓이는 모든 경우의 수를 체크해도 풀립니다. 저는 모든 경우의 수를 체크할때 비트마스킹을 사용했습니다. 킹 퀸 룩 비숍 모두 8개의 좌표 두개로 방향이 표시됩니다. 저같은 경우 조건문을 복사 붙여넣기로 코드가 길어졌는데 좀 더 깔끔하게 푸실 수 있을것 같습니다. #include #include #includ.. 백준 23302 전파와 병합 2 http://www.acmicpc.net/problem/23302 23302번: 전파와 병합 2 첫째 줄에 열과 행의 크기 R, C 가 각각 주어진다.(1 ≤ R ≤ 999 , 1 ≤ C ≤ 702) 둘째 줄부터 스프레드 시트의 각 칸이 참조하는 셀의 좌표가 주어진다. 알파벳 대문자는 A부터 첫 번째 행을 나타 www.acmicpc.net dfs를 사용해 문제를 풀었습니다. 그래프의 사이클 유무를 체크하는 간단한 문제지만 그래프의 연결관계가 문자열로 주어지므로 추가로 문자열처리 파싱이 요구되는 문제였습니다. 저는 문자열을 뒤에서 부터 읽어 진법을 처리하였고 +를 만나면 추가로 연결관계를 기록하게 했습니다. 사이클 체크는 dfs로 시작점을 인자로 주어 현재위치가 시작점으로 돌아올경우 사이클이 존재한다고 판.. 백준 11689 GCD(n, k) = 1 http://www.acmicpc.net/problem/11689 11689번: GCD(n, k) = 1 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 포제의 원리를 사용해서 푸는 문제였습니다. 소인수 분해를 한후 소인수들을 이용해 포제의 원리를 통해 답을 구하면 됩니다. 저는 비트마스킹을 통해 포함 제외를 구현했습니다. #include #include #include #include #include #include #include #include using namespace std; void fast_io() { cin.tie(0)->sync_with_stdio(0); } long long N.. 백준 15659 연산자 끼워놓기 (3) http://www.acmicpc.net/problem/15659 15659번: 연산자 끼워넣기 (3) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 재귀를 통해 푸는 문제였습니다. 모든 경우를 체크해도 O(4^11)이므로 최적화 없이 경우의 수에 따른 결과 계산만 하면 됩니다. 저는 바텀업 방식으로 구현했는데 다른분들 코드를 보니 탑다운이 좀 더 깔끔하고 직관적이었던것 같습니다. 곱셈과 나눗셈부분이 구현하기 까다로웠는데 저는 후위표기식 구현처럼 스택에 곱셈과 나눗셈을 넣은뒤 덧셈 뺄.. 백준 18234 당근 훔쳐 먹기 http://www.acmicpc.net/problem/18234 18234번: 당근 훔쳐 먹기 첫 번째 줄에 N(1 ≤ N ≤ 200,000)과 T(N ≤ T ≤ 100,000,000)가 공백으로 구분되어 주어진다. 오리는 당근의 맛을 충분히 높이기 위해 항상 N이상인 T일 동안 재배한다. 다음 N개의 줄에 걸쳐서 i+1번째 www.acmicpc.net 정렬을 사용하는 그리디 문제였습니다. 초기값 Wi가 주어지고 시간이 1씩 지날수록 Pi만큼 맛이 커지는데 Pi는 Wi보다 크다는 조건이 있습니다. 따라서 Wi를 바로 먹기보다 시간이 지나고 먹는게 무조건 크다는걸 알 수 있습니다. 이를 적용하면 Pi가 클수록 가능한 늦게먹으면 됩니다. T가 N보다 크므로 T-N부터 Pi가 작은거부터 먹기 시작하면 됩니다.. 백준 22985 문자열 조작의 달인 http://www.acmicpc.net/problem/22985 22985번: 문자열 조작의 달인 나올 수 있는 문자열은 cy, bz, az의 $3$개이다. www.acmicpc.net DP문제였습니다. 처음에는 조합론문제일줄 알았는데 문자열에 변화를 가할떄 'z'에도 변화를 가할 수 있으므로 중복조합으로 풀 수 없다는 걸 알고 DP로 풀었습니다. 최대 변화 횟수는 10^18이지만 나올 수 있는 문자열 자체는 한정되어있다는걸 알 수 있습니다. 길이가 최대 300인 문자열에 변화를 줄 수 있는 최대횟수는 전부 'a'로 이루어졌다고 가정해도 25*300이 최대입니다. 따라서 우리는 주어진 문자열에서 가할 수 있는 최대 변화회수를 구하고 거기에 맞추면 됩니다. DP로 문자열의 상태를 구할때 주의해야될점은 z.. 이전 1 2 3 4 5 6 7 8 다음
