전체 글
-
[17413] 단어 뒤집기 2BOJ 2022. 5. 14. 13:47
https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 아마 스택을 사용하면 조금 더 깔끔하게 짤 수 있을 것 같다. ''이 나올때까지 그대로 출력하고 continue ' '이 나오면, 단어를 출력한다. 루프가 끝난 다음에도 아직 출력하지 않은 단어가 존재할 수 있으므로 한번 더 체크해준다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local =..
-
[17485] 진우의 달 여행 (Large)BOJ 2022. 5. 14. 13:40
https://www.acmicpc.net/problem/17485 17485번: 진우의 달 여행 (Large) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2 ≤ N, M ≤ 1000)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net dp[n][m][3] 형태로 테이블을 만들어서, 현재 방향과 다른 방향인 곳 2개중 작은것을 취한다. 편의상 1-base index를 사용하고, [1..n][1..m]이 아닌 다른곳은 INF로 채워주어서 방향을 신경쓰지 않고 min()으로 선택하는 도중에 자연스럽게 배제되도록 하였는데, 계산 과정중 a[i][j] + INF가 INT_MAX를 넘으면 문제가 될..
-
[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..
-
lazy 세그템플릿 2022. 5. 2. 01:10
https://www.acmicpc.net/problem/10999 #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; vector a, segTree, lazy; void updateLazy(ll i, ll s, ll e) { if (lazy[i] != 0) { segTree[i] += (e - s + 1) * lazy[i]; if (s != e) { lazy[i * 2] += lazy[i]; lazy[i * 2 + 1] += lazy[i]; } lazy[i] = 0; } } l..
-
[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개만 모든 경우로 배치한 후를 생각..