본문 바로가기

대딩192

[백준 1629번] 곱셈 풀이 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net A^B % C 를 구하는 문제이다. A와 B의 최댓값이 2147483647 이므로, 직접 A^B를 구해 C로 나누면 오버플로우가 발생하게 된다. 따라서 다음 두가지 사실과 분할 정복 방법을 이용하여 문제를 해결해보고자 한다. 1. A^B는 B가 짝수인지 홀수인지에 따라 A^(2/B)의 곱으로 나타낼 수 있다. 예를 들어, B = 10 일 때, A^10 = A^5 * A^5 이다. B = 9 일 때, A^9 = A^4 * A^4 * A 이다. 즉, B%2 == 0 (B가 짝수) 일 때, A^B = A^(2/B) * A^(2/B).. 2021. 10. 12.
[백준 1149번] RGB 거리 풀이 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 집 N개를 각각 빨강(r), 초록(g), 파랑(b)으로 칠할 때의 비용이 주어진다. i번째 집은 i-1 번째 집과 다른 색으로 칠해져야 한다. N개의 집에 대하여 칠할 수 있는 모든 조합을 탐색하면, //R로 시작하는 경우 R / G / \ / B R ... \ R \ / B \ G 경우의 수가 2의 거듭제곱으로 늘어 시간 복잡도는 3 * 2^(N-1) 이 된다. 해당 방법은 시간 초과가 예상되므로, 다이내믹 프로그래밍(dp) 점화식을 세워.. 2021. 10. 11.
[백준 16139번] 인간-컴퓨터 상호작용 풀이 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 문자열 S가 주어졌을 때, l 부터 r까지의 인덱스 중 알파벳 a의 개수를 출력하는 문제이다. a, l, r 이 q번 주어질 때마다 문자열을 일일이 탐색하여 해결할 수도 있겠지만 시간 초과가 발생할 것으로 예상된다. 해당 문제는 구간합 개념으로 쉽게 해결할 수 있다. 0 1 2 3 4 5 6 7 8 9 10 11 12 //idx s e u n g j a e h w a n g //s[idx] 0 1 1 1 1 1 1.. 2021. 10. 7.
[백준 14465번] 소가 길을 건너간 이유 5 풀이 14465번: 소가 길을 건너간 이유 5 첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다. www.acmicpc.net N개의 신호등 중 B개가 고장 나 있을 때, 연속으로 K개가 존재하도록 고쳐야 하는 최소 신호등의 개수를 출력하는 문제이다. N = 10, B = 5, K = 6 일 때, 최소로 고쳐야 하는 신호등의 개수를 구하기 위해 1개를 고치는 경우부터 B개를 고치는 경우까지 모두 확인할 수도 있다. 그러나 이 방법은 높은 시간 복잡도를 가진다. 슬라이딩 윈도우 기법을 이용하여 연산 과정을 줄여보자. 슬라이딩 윈도우 기법은 연속된 영역에서 특정 값을 계산하여 비교할 때 사용한다. 슬라이딩 + 윈도우 = 미끄러지는 창문이라는 뜻으.. 2021. 10. 5.
[백준 10819번] 차이를 최대로 풀이 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 배열의 크기 N과 요소들이 주어졌을 때, 배열의 순서를 적절히 바꾸어 sum = |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 의 최댓값을 구하는 문제이다. 재귀 함수를 통해 배열의 순서를 정하고, sum의 최댓값을 구하는 방법이 있다. 먼저 원소의 개수 N과 배열 A를 초기화시키자. scanf("%d", &N); memset(A, 0, sizeof(A)); for (int i=0; i 2021. 10. 4.
[백준 16488번] 피카츄가 낸 어려운 문제 풀이 16488번: 피카츄가 낸 어려운 문제 맨날 학교 칠판에 이등변삼각형을 그리고 노는 피카츄가 어느 날, 칠판에 변 AB와 변 AC의 길이가 모두 N인 이등변 삼각형을 그린 다음, 친구들에게 아래와 같은 문제를 냈다. 이등변삼각형 ABC에 www.acmicpc.net 변 AB = AC인 이등변 삼각형의 밑변 BC에 P1 ... PK 까지의 점을 두었다. 우리가 구해야 하는 값은 다음과 같다. $$ \sum_{i=1}^K F(i) = \sum_{i=1}^K ( \overline{APi}^2 + \overline{BPi} * \overline{CPi} ) $$ 먼저, APi^2 을 계산해보자. 삼각형 A Pi D 는 직각삼각형을 이루고 있으므로 피타고라스 공식에 의해 다음과 같다. $$ \overline{AP.. 2021. 10. 2.
[백준 14930번] 구슬 (BEAD) 풀이 #백준 #백준 14930번 #백준 구슬 (BEAD) 14930번: 구슬 (BEAD) 물리를 사랑하는 민준이는 집에 마찰이 없는 무한한 수직선과 완전탄성충돌을 하고 질량이 동일하며 크기를 무시할 수 있는 구슬 N(1 ≤ N ≤100,000)개를 구비해놓고 있다. 어느 날 민준이는 모션 www.acmicpc.net 이 문제는 백준 4307번 개미와 유형이 비슷한 문제로, 수직선 위에서 개미나 구슬 등의 물체들이 충돌할 때 결과를 구하는 문제이다. 이러한 유형의 문제를 해결하기 위해서는 두 가지 사실을 알아야 한다. 1) t초 후 구슬들의 순서는 변하지 않는다. 2) 완전탄성충돌한 두 구슬은 속도가 교환된다. 첫번째 전제 부터 살펴보면, 초기 위치가 3인 구슬은 초기 위치가 -2인 구슬과 초기 위치가 4인 구.. 2021. 10. 2.
[백준 538번] 제곱근 작도 풀이 5389번: 제곱근 작도 첫 번째 줄에는 테스트 케이스의 개수가 주어진다. 다음 줄부터 각각의 테스트 케이스에 대해 정수 1 ≤ N ≤ 109 이 한 줄마다 주어진다. www.acmicpc.net H에서 y 사이의 거리를 r, H에서 x 사이의 거리를 l, x와 y 사이의 거리를 루트 n 이라 할 때, 세 변은 직각삼각형을 이루고 있으므로 다음을 만족한다. $$ (\sqrt{n})^2 + l^2 = r^2$$ 문제에서는 n 값을 알려주고 있으므로, 위의 식을 만족시키는 l과 r의 값 중 가장 작은 값들을 구하면 된다. 수식을 변형해보면, $$(\sqrt{n})^2+l^2 = r^2 (r > l)$$ $$ (\sqrt{n})^2 = r^2 - l^2$$ $$n = (r + l)*(r - l)$$ r + l.. 2021. 9. 30.
[백준 2504번] 괄호의 값 풀이 #백준 #백준 2504번 #백준 괄호의 값 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 중첩되는 괄호에 대해 값을 저장하고 계산하는 문제이다. 괄호의 중첩은 스택을 이용하여 해결할 수 있다. 먼저, 입력된 문자열을 저장하고 스택을 생성한다. string s; cin >> s; stack st; 이후, 입력된 문자열의 각 자릿값을 판별하여 처리한다. (()[[]])([]) 문자열의 자릿값이 ( 이고 닫는 괄호가 이어지지 않는 경우 스택에 문자열 "(" 을 저장한다. //stack ( 문자열의 자릿값이 ( .. 2021. 9. 30.
[백준 4307번] 개미 풀이 4307번: 개미 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 막대의 길이와 개미의 수 n이 주어진다. 다음 n개 줄에는 숫자가 하나씩 주어지며, 이 숫자는 개미의 초기 위치를 www.acmicpc.net T개의 테스트 케이스에 대하여 막대의 길이 L과 개미의 수 N이 주어진다. 개미는 모두 1m/s로 이동하고 충돌시 반대 방향으로 움직인다. '개미가 서로 충돌할 때 반대 방향으로 움직인다'는 조건은 고려하지 않아도 된다. 그 이유를 살펴보면, 1차원 상의 좌표에 반대방향으로 움직이는 두 개미가 있다. 두 개미가 충돌하면 각 개미의 진향 방향이 반대가 되므로, 다음과 같은 과정을 거친다. 문제에서 모든 개미를 똑같이 취급하고 있으므로(개미에게 번호를 부여한다던가... 그런.. 2021. 9. 29.

티스토리툴바