BOJ
-
[14607] 피자 (Large)BOJ 2022. 5. 13. 20:46
https://www.acmicpc.net/problem/14607 14607번: 피자 (Large) 예제1의 입력이 1이므로, 게임 시작부터 갑이 분리할 수 있는 피자탑이 없습니다. 따라서 갑이 얻는 즐거움은 0입니다. 예제2의 정답 3은 다음과 같은 과정을 통해 얻어집니다. 먼저 놀이를 시작 www.acmicpc.net 초기항 몇개를 직접 계산해보면, 규칙성이 보인다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; using pi = pair; int main(void) { if (!local..
-
[2312] 수 복원하기BOJ 2022. 5. 2. 02:06
https://www.acmicpc.net/problem/2312 2312번: 수 복원하기 첫째 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스마다 양의 정수 N (2 ≤ N ≤ 100,000)이 주어진다. www.acmicpc.net 소인수분해후 인수의 개수를 a[i]에 저장하고, a[i]>0일때 i와 a[i]를 출력하자 #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; using pi = pair; int a[100001]; int main(void) { if (!local) ios_bas..
-
[1283] 단축키 지정BOJ 2022. 5. 2. 02:04
https://www.acmicpc.net/problem/1283 1283번: 단축키 지정 첫째 줄에 옵션의 개수 N(1 ≤ N ≤ 30)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄에 옵션을 나타내는 문자열이 입력되는데 하나의 옵션은 5개 이하의 단어로 표현되며, 각 단어 역시 10개 이하 www.acmicpc.net 공백을 단축키로 지정하지 않도록 주의할 필요가 있다. set에 대문자와 소문자를 항상 같이 넣어줌으로 "대소문자를 구분하지 않음" 을 구현할 수 있다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll..
-
[24445] 알고리즘 수업 - 너비 우선 탐색 2BOJ 2022. 5. 2. 02:02
https://www.acmicpc.net/problem/24445 24445번: 알고리즘 수업 - 너비 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 인접리스트를 역순으로 정렬해두고 실제로 bfs를 돌리면서 순서를 기록해두자 #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long lo..
-
[15967] 에바쿰BOJ 2022. 5. 2. 01:09
https://www.acmicpc.net/problem/15967 15967번: 에바쿰 재성이가 재혁이를 때린 날수 N과 재성이가 변덕을 부린 날의 개수 Q1, 재혁이가 얼마나 맞았는지 궁금한 구간의 개수 Q2가 주어진다. (1 ≤ N ≤ 1,000,000, 0 ≤ Q1, Q2 ≤ 10,000) 그 다음줄엔 재혁이가 i www.acmicpc.net 구간합쿼리, 구간업데이트이므로 "[10999] 구간 합 구하기 2" 와 같은 문제 #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; ll n, m, k;..
-
[13900] 순서쌍의 곱의 합BOJ 2022. 4. 27. 12:06
https://www.acmicpc.net/problem/13900 13900번: 순서쌍의 곱의 합 첫 번째 줄에는 입력 받을 정수의 개수 N(2 ≤ N ≤ 100,000) 두 번째 줄에는 N 개의 정수가 주어진다. 이때 입력 받는 정수들의 범위는 0이상 10,000 이하이다. www.acmicpc.net 예제 1은 (2*3) + (2+3)*4, 예제 2는 (1*2) + (1+2)*3 + (1+2+3)*4..와 같은 방식으로 계산하자. 누적합을 구하고, a[1]부터 참조하여 식을 만들어주었다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #end..
-
[2784] 가로 세로 퍼즐BOJ 2022. 4. 27. 01:11
https://www.acmicpc.net/problem/2784 2784번: 가로 세로 퍼즐 6개 단어를 3*3 가로 세로 퍼즐에 놓을 수 없다면 0을 출력한다. 그렇지 않다면, 3개 줄에 퍼즐을 출력한다. 만약 가능한 답이 여러개라면 사전순으로 앞서는 것을 출력한다. 사전순으로 비교를 할 www.acmicpc.net 디스크립션의 처음 부분이 무슨 뜻인지는 잘 모르겠지만, 어쨋든 길이3의 문자열 6개가 들어오고, 3*3의 공간에 알파벳을 배치한 후 왼쪽과 위에서 3글자씩 읽었을때 생긴 6개의 문자열이 동일한 경우를 찾는다. 여러개가 나올경우 왼쪽위부터 오른쪽 아래로 읽은 길이9의 문자열을 사전순 비교했을때 가장 앞에오는 경우가 답이다. 초기에 입력된 6개의 문자열중 3개만 모든 경우로 배치한 후를 생각..
-
[1107] 리모컨BOJ 2022. 4. 25. 00:42
https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 적당히 큰 범위를 잡아서, 고장난 버튼이 없어서 그 채널로 숫자를 입력해서 이동이 가능할때 그 채널의 자리수의 개수(string.length())와, 그 채널에서 n까지 가기 위해 필요한 +, -의 횟수(abs(n - i))를 최소로 갱신 #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; ..
-
[14500] 테트로미노BOJ 2022. 4. 22. 15:32
https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 일자형만 제외하면 3*2의 직사각형에서 2개만 제외하여 만들 수 있다. 일자형은 별도로 계산하고, 직사각형에서 2개씩 빼준 값을 업데이트 하는 방식으로 구현했다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll =..
-
[3584] 가장 가까운 공통 조상BOJ 2022. 4. 15. 15:59
https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 루트만 찾아서 lca로 구했다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; using pi = pair; constexpr int M..