https://www.acmicpc.net/problem/1769 1769번: 3의 배수 문제가 잘 풀리지 않을 때, 문제를 바라보는 시각을 조금만 다르게 가지면 문제가 쉽게 풀리는 경험을 종종 해 보았을 것이다. 여러 가지 방법이 있지만 그 중 하나로 우리가 풀고 싶은 문제를 www.acmicpc.net 문제 큰 자연수 X가 주어질 때, 각 자릿수의 합이 한 자리수가 될 때 까지 몇 번의 과정을 거쳤는지 출력하고, 둘째 줄에는 그 한 자리 수가 3의 배수이면 "YES", 아니면 "NO"를 출력한다. 풀이 - 큰 수는 1,000,000 자리 이하의 수임에 주의한다. -> string 이용 - cnt++를 해주며 횟수를 저장하고, s의 각 자릿수의 합을 계산한다. #include #include using..
Koala - 14기/코딩테스트 준비 스터디
https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 요세푸스 문제 비슷한 유형이다. 원형 큐 혹은 덱을 사용해서 풀 수 있는데 나는 덱을 이용하여 풀었다. 일단 문제를 해결하기 위해서 값을 빼낼 위치 한 곳을 정해주어야 한다. 왼쪽으로 이동, 오른쪽으로 돌리는 연산은 각각 append(popleft())와 appendleft(pop())로 구현을 할 수 있다. 맨 처음 덱의 상태이다. 3 2 1 -3 -1 popleft해준 뒤 나..
https://www.acmicpc.net/problem/25603 25603번: 짱해커 이동식 첫 번째 줄에 정수 $N$, $K$가 주어진다. ($1 \le K < N \le 100\,000$) 두 번째 줄부터 $N$개의 기업 의뢰의 비용이 주어진다. 비용은 $1$ 이상 $10^9$ 이하의 정수이다. www.acmicpc.net 알고리즘 분류 자료구조 우선순위 큐 매개 변수 탐색 이분탐색 문제 짱해커 이동식은 상대방의 디스크에 자신의 이름을 남겨 자신이 왔다간 것을 알린다. 이동식에게 인정받기 위해 오늘도 수많은 기업들의 보안담당자들은 모의해킹 의뢰를 하기 위해 줄을 선다. 모든 의뢰를 받아들이기엔 너무 부담이 됐기 때문에, 각 의뢰들을 수행하는 데 필요한 비용을 측정해 최대한 비용이 적게 드는 의뢰들..
19951번: 태상이의 훈련소 생활 (acmicpc.net) 19951번: 태상이의 훈련소 생활 2020년 5월 14일 논산훈련소에 입대한 태상이는 첫 총기 훈련에서 가스 조절기를 잃어버리는 중대한 실수를 범했다. 그로 인해, 태상이는 조교들에게 눈총을 받게 되었다. 조교들은 태상이에게 연 www.acmicpc.net 코드 n,m=map(int,input().split()) A=list(map(int,input().split())) pr_sum = [0 for i in range(n+2)] for j in range(m): a,b,k=map(int,input().split()) pr_sum[a]+=k pr_sum[b+1]-=k for i in range(n): pr_sum[i+1]+=pr_sum[i] f..
https://www.acmicpc.net/problem/1455 1455번: 뒤집기 II 세준이는 동전 뒤집기를 하려고 한다. 세준이는 동전을 N×M개 가지고 있다. 동전은 세로로 N개, 가로로 M개 크기의 직사각형에 차곡차곡 놓여져 있다. 동전의 앞면을 0이라고 하고 뒷면을 1이라고 www.acmicpc.net 코드 #include #include #include #include #include #include #include #include #include #include #include #include #include #define LL long long using namespace std; int arr[101][101]; void reverse(int a, int b) { for (int i ..
문제 https://www.acmicpc.net/problem/30088 Algorithm 각 부서별로 면담 시간의 합이 적은 순서대로 정렬한 뒤, 누적합을 구하여 출력한다. Code #include #include #include using namespace std; #define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0); typedef long long ll; typedef pair pii; typedef pair pll; ll n; vector v; void INPUT() { IAMFAST cin >> n; for (int i = 0; i > num; ll sum = 0; while (num--) { ..
문제 링크 https://www.acmicpc.net/problem/17179 17179번: 케이크 자르기 첫 번째 줄에 자르는 횟수가 담긴 목록의 길이 N과 자를 수 있는 지점의 개수 M, 그리고 롤 케이크의 길이인 정수 L이 주어진다. (1 ≤ N ≤ M ≤ 1,000, 1 < L ≤ 4,000,000) 다음 M줄에 걸쳐 자를 수 있는 www.acmicpc.net 풀이 다음과 같이 접근하여 문제를 해결하였다. 1. 케이크를 Q_i 자를 때 생기는 가장 작은 조각의 최댓값의 최적해를 X라고 가정한다. 2. 실제로 케이크를 Q_i번 잘랐을 때 X가 가능한 해인지 확인한다. 3. 가능하다면 X보다 큰 X + k를 새로운 최적해로 가정한다. 불가능하다면 X보다 작은 X - k를 새로운 최적해로 가정한다. 4..
https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 문제요약 주어진 알고리즘 대로 격자내에 드래곤 커브를 그린다. 격자내에서 드래곤 커브에 둘러쌓인 1x1 사각형이 모두 몇개인지 출력한다. 문제해결 새로 생기는 드래곤 커브들의 방향을 결정할 때, 이전에 생겼던 커브를 가장 최근에 생긴 순서대로 읽으면서, 그 커브의 방향에 +1을 하면 새로운 커브들의 방향이 결정된다. 이를 스택을 이용하여 풀었다. 코드 #include #..
문제 https://www.acmicpc.net/problem/19637 Algorithm 처음엔 딕셔너리로 정의했는데 key, value로 변환하기 까다로웠다. 이러한 케이스는 다음과 같이 각각의 두 개의 리스트를 정의 → 인덱스 쌍으로 찾을 수 있다는 점을 알게되었다. # 칭호 정보 저장 | name_arr, val_arr은 같은 인덱스로 값을 찾을 수 있다. for _ in range(n): name,value=input().split() name_arr.append(name) val_arr.append(int(value)) # ... 생략 # val_arr로부터 원하는 값을 찾는다. if target
https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이 www.acmicpc.net 알고리즘 분류 자료구조 세그먼트 트리 이분탐색 문제 수정이는 어린 동생을 달래기 위해서 사탕을 사용한다. 수정이는 평소에 여러 개의 사탕을 사서 사탕상자에 넣어두고, 동생이 말을 잘 들을 때면 그 안에서 사탕을 꺼내서 주곤 한다. 각각의 사탕은 그 맛의 좋고 나쁨이 1부터 1,000,000까지의 정수로 구분된다. 1이 가장 맛있는 사탕을 의미하며, 1,000,000은 가..
https://www.acmicpc.net/problem/11576 11576번: Base Conversion 타임머신을 개발하는 정이는 오랜 노력 끝에 타임머신을 개발하는데 성공하였다. 미래가 궁금한 정이는 자신이 개발한 타임머신을 이용하여 500년 후의 세계로 여행을 떠나게 되었다. 500년 후의 www.acmicpc.net 문제 입력에 a, b (2> a >> b; cin >> m; for (int i = 0; i > arr[i]; } for (int i = 0; i < m; i++) { total += arr[m-1-i] * idx; idx *= a; } long long tmp = 1; while (tmp
구간 합 구하기 4 !https://d2gd6pc034wcta.cloudfront.net/tier/8.svg 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 112189 46204 34089 38.867% 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. 제한 1 ≤ N ≤ 100,000 1 ≤ M ≤ 100,000 1 ≤ i ≤ j..
