BOJ
-
[2609] 최대공약수와 최소공배수BOJ 2021. 10. 1. 16:30
https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 최대공약수는 반복문에서 하향식으로 내려오다, 공약수일때 break하면 됩니다. 또한, 최소공배수는 두 수를 곱하고 최대공약수로 나누면 곧 최대공배수가 됩니다. 입력이 작아 유클리드 알고리즘을 사용하지 않아도 TLE가 발생하지 않습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 #include #include using namespace std; int main(void) { int i, x, y; scanf("%d %d", &x, &y); for (i..
-
[1789] 수들의 합BOJ 2021. 10. 1. 16:23
https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 최저의 경우는, 1 + 2 + 3 + ... + N-2 + N-1 + N 과 같은 경우일 것이므로 1부터 N까지의 누적합이 초과하기 '이전의' N을 초과하면 된다. 1부터 N까지의 누적합을 dp[n]에 넣는다면, 'dp[n] > n; for (i = 1;; i++) { sum ..
-
[11659] 구간 합 구하기 4BOJ 2021. 9. 30. 07:31
https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 모든 k에 대해 [1, k]까지의 합을 알고 있다면 아래의 식을 이용해서 매 쿼리당 O(1)만에 답을 구할 수 있다. sum[s, e] = sum[1, e] - sum[1, s - 1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include int n, m; int a[100001], dp[100001]; int main(void) { i..
-
[1963] 소수 경로BOJ 2021. 9. 30. 07:20
https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 에라토스테네스의 체(전처리) + bfs(최적해 계산)로 접근했다. 이 문제에 적용된 bfs에서 다음 정점은 아래의 조건을 만족해야 한다. 1. 소수 2. 자리수중 한개만 변화 3. 아직 방문하지 않은 상태 이중 소수의 목록을 미리 구함으로서 매 정점마다 (9999-1000+1)개의 수를 탐색하는 것이 아닌, [1000, 9999]중 소수의 개수만큼만 탐색할 수 있다. (2)의 판별은 아래 소스코드의 che..
-
[1439] 뒤집기BOJ 2021. 9. 30. 07:06
https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 입력받은 문자열 s를 1로 만드는 경우와 0으로 만드는 경우 2가지로 나누고, 1로 만드는 경우에는 0이 한데 붙어있는 구간의 수, 0으로 만드는 경우에는 1이 한데 붙어있는 구간의 수를 카운트하고 이중 작은 것을 출력하면 최적해를 찾을 수 있습니다. 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 #include using n..
-
[1339] 단어 수학BOJ 2021. 9. 30. 06:52
https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 자리수가 가장 큰 수부터 9..8..7 순서로 배정하면 된다. 가령, 2 ABCD EFG 같은 입력이 들어오면 A(4) -> B,E(3) -> C,F(2) -> D,G(1)의 순서로 9부터 0까지 배정한다는 뜻이다. B에 8을 배정하고 E에 7을 배정하든, B에 7을 배정하고 E에 8을 배정하든 아무 상관이 없다 (700 + 800) = (800 + 700) 1 2 3 4 5 6 7 8 9 ..
-
[1541] 잃어버린 괄호BOJ 2021. 9. 28. 17:29
https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net stoi()를 사용해서 파싱은 간단하게 구현할 수 있다. '-'가 나온 뒤로부터는 항상 숫자를 빼주고, 그 전까지는 항상 숫자를 더해주면 된다. 가령 - 1 + 2 - 3 + 4 + 5 --> - (1+2) - (3+4+5) 처럼, -를 경계로 +들을 합치는 방식으로 괄호를 쳐주면 된다. 고로 연산자들의 배열과 관계없이, '-' 연산자가 처음으로 등장한 시점만이 어떤 수를 더하고 뺄지에 영향..
-
[1092] 배BOJ 2021. 9. 28. 02:12
https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 그리디 : 무게 제한이 높은 순으로, 무거운 박스부터 옮긴다(정렬) (가장 무게제한이 높은 크레인) < (가장 무거운 박스) 일때에만 -1을 출력하면 되고, 그밖에는 모두 해가 존재한다. 입력을 vector로 받고, bfs처럼 while(!v.empty())로 간단하게 구현할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21..
-
[14226] 이모티콘BOJ 2021. 9. 27. 03:06
https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net bfs로 푼다면 state를 { cur : 현재 화면에 있는 이모티콘의 개수 clip : 현재 클립보드에 있는 이모티콘의 개수 turn : 현재까지 걸린 시간 } 처럼 구성해주면 된다. dp로도 풀릴것 같았고, 실제로 solved.ac의 분류에도 다이나믹이 있었다. 처음에는 2차원을 생각했다. 아래처럼 구성하면 O(N^2)안에 풀릴것으로 생각했다. dp[i][j] : i개의 이모티콘을 출력(cur)..
-
[1254] 팰린드롬 만들기BOJ 2021. 9. 27. 02:52
https://www.acmicpc.net/problem/1254 1254번: 팰린드롬 만들기 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 www.acmicpc.net 입력되는 문자열의 오른쪽에 0개 이상의 문자를 추가해, 팰린드롬을 만들어야 한다. 이때, 추가하는 문자의 최소값을 구하는 문제다. 입력되는 문자열을 s로 부르면, 팰린드롬을 만족하는 s의 부분문자열 [start, end]의 길이 len = end - start + 1이 길어질 수록 최적해에 가깝다. 길이 5의 s가 입력될때, 2번째~5번째 문자가 팰린드롬을 만족한다면 1번째 문자를 6번째 문자로 추가적..