반응형

백준 249

[백준 / BOJ] C++ 27968 사사의 사차원 사탕 봉지

27968번: 사사의 사차원 사탕 봉지 문제 https://www.acmicpc.net/problem/27968 27968번: 사사의 사차원 사탕 봉지 첫 번째 줄에 아이의 수 $N$과 사사가 사탕을 꺼내주려고 하는 최대 횟수 $M$이 공백으로 구분되어 주어진다. ($1 \le N \le 300 \, 000$, $1 \le M \le 300 \, 000$) 두 번째 줄에 사사가 한 번에 사탕을 꺼내는 www.acmicpc.net 풀이 누적 합 + 이분 탐색 문제로 사탕을 꺼낼 때마다 사탕의 수는 누적되므로 몇 번 꺼냈을 때 사탕이 얼마나 있는지 알 수 있다. 그리고 아이가 받고 싶어하는 사탕의 수가 정확히 꺼낸 수와 동일하지 않을 수 있으므로 lower_bound 함수로 최초로 같거나 큰 수의 사탕이 있..

Problem Solving/BOJ 2023.04.19

[백준 / BOJ] C++ 27966 △

27966번: △ 문제 https://www.acmicpc.net/problem/27966 27966번: △ $N$개의 정점으로 이루어진 트리의 모든 정점 쌍에 대하여, 두 정점 사이의 거리의 합을 최소화하시오. 정점에는 $1$부터 $N$까지 번호가 매겨져 있다. 즉, 정점 $i$와 정점 $j$ 사이의 거리를 $\textrm www.acmicpc.net 풀이 문제 처음 보자마자 떠오른 생각이 별 모양 트리, 성형 트리다. 가운데 정점 하나에 모든 다른 정점들이 연결되어 있는 트리 형태로 가운데 정점으로부터 다른 모든 정점까지의 거리는 1, 이외는 모두 2인 트리다. 따라서 n - 1 + 2 * nC2 가 거리의 합이 되고, 가운데 정점을 1이라고 하면 1 2 ~ 1 n까지 모두 출력하면 된다. nC2 계..

Problem Solving/BOJ 2023.04.19

[백준 / BOJ] C++ 27964 콰트로치즈피자

27964번: 콰트로치즈피자 문제 https://www.acmicpc.net/problem/27964 27964번: 콰트로치즈피자 치즈와 피자에 환장하는 비행씨는 매일같이 치즈피자를 사 먹다가 지갑이 거덜 나고 말았다. 만들어 먹는 것이 사 먹는 것보다 싸다는 것을 안 비행씨는 여러 가지 토핑을 가져와서 직접 피자를 www.acmicpc.net 풀이 서로 다른 치즈가 4종류 이상 존재하느냐가 중요하다. Cheese의 크기는 6이므로 문자열 크기가 5 이하인 문자열은 예외처리를 해줘야 한다. 그리고 나머지 문자열에 대해 마지막 글자 6글자가 Cheese인지 검사하면 된다. 중복 처리를 위해 map 자료형을 사용한다. map의 크기가 4 이상이면 yummy를 출력하고 아니면 sad를 출력한다. 코드 #inc..

Problem Solving/BOJ 2023.04.18

[백준 / BOJ] C++ 27963 합금 주화

27963번: 합금 주화 문제 https://www.acmicpc.net/problem/27963 27963번: 합금 주화 첫 번째 줄에 0보다 크고 100보다 작은 세 정수 $d_1$, $d_2$, $\chi$가 공백으로 구분되어 주어진다. 서로 다른 두 정수 $d_1$, $d_2$는 기념주화를 이루는 두 가지 금속의 밀도이다. 단위는 $\text{g}/\text{cm} www.acmicpc.net 풀이 d1, d2를 d1 < d2로 재배열한 다음 질량 비율을 구하기 위해 p를 계산해 주고 적절히 식을 세워 답을 얻을 수 있다. 자세한 설명은 아래 이미지와 코드로 대체하겠다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); ..

Problem Solving/BOJ 2023.04.18

[백준 / BOJ] C++ 27962 오렌지먹은지오랜지

27962번: 오렌지먹은지오랜지 문제 https://www.acmicpc.net/problem/27962 27962번: 오렌지먹은지오랜지 오렌지를 먹은 지 오래된 선생님은 부족한 비타민C를 문자열 문제를 통해 보충하려고 한다. "오렌지 먹은 지 오랜지"의 "오렌지", "오랜지"와 같이, 길이가 동일하며 각각 맨 앞, 맨 뒤 문자를 포 www.acmicpc.net 풀이 앞과 뒤에서부터 각각 길이가 1에서 N까지인 문자열을 한 자리씩 비교해 다른 문자가 1개만 있으면 YES를 출력하고 프로그램을 종료한다. 모두 비교했는데 YES를 출력하지 않았다면 NO를 출력한다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0..

Problem Solving/BOJ 2023.04.18

[백준 / BOJ] C++ 27961 고양이는 많을수록 좋다

27961번: 고양이는 많을수록 좋다 문제 https://www.acmicpc.net/problem/27961 27961번: 고양이는 많을수록 좋다 올바른 행동 순서가 될 수 있는 하나의 예시는 아래와 같으며, $4$번보다 더 작은 행동 횟수로 $6$마리의 고양이를 마도카의 집에 들이는 것은 불가능하다. 초기 상태($0$마리) $\rightarrow$ 생성 www.acmicpc.net 풀이 처음에 고양이는 0마리 있고, 1마리 생성하거나 현재 K마리의 고양이가 있으면 1~K마리의 고양이를 복제하는 것이 가능하다. 즉, 고양이가 1마리 이상 있을 때는 복제 연산만 사용하면 된다. 이때, 정확히 N마리의 고양이를 만들어야 하므로 2 * K ≥ N 이 되는 순간 연산이 종료된다. 따라서 2의 제곱승 꼴로 증가..

Problem Solving/BOJ 2023.04.17

[백준 / BOJ] C++ 27960 사격 내기

27960번: 사격 내기 문제 https://www.acmicpc.net/problem/27960 27960번: 사격 내기 A, B, C는 올해에도 예비군 훈련을 받으러 간다. 이번 예비군 훈련 과정 중에는 영점 사격이 있으며, 10개의 과녁 각각에 점수를 매겨 맞춘 과녁 점수의 총합을 측정한다. 과녁을 맞혔을 때, 과녁별 www.acmicpc.net 풀이 과녁의 점수가 2의 n승 꼴의 연속이므로 어느 과녁을 맞췄는지 점수만으로 알 수 있다. 따라서 점수를 2진법으로 변환한 다음 XOR 연산을 수행해 다시 10진수로 바꾸어 출력하면 된다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int a, b; ..

Problem Solving/BOJ 2023.04.17

[백준 / BOJ] C++ 27959 초코바

27959번: 초코바 문제 https://www.acmicpc.net/problem/27959 27959번: 초코바 밤고는 $100$원 동전을 $N$개 갖고 있고, 그 돈으로 가격이 $M$원인 초코바를 사 먹으려고 한다. 밤고는 갖고 있는 돈으로 초코바를 사 먹을 수 있는지 알고 싶어 한다. 밤고가 가진 돈이 초코바의 www.acmicpc.net 풀이 100원 동전 N개로는 100 * N원 이하의 초코바만 살 수 있으므로 100 * N ≥ M인 경우 초코바를 살 수 있다. 이 경우 Yes를 출력하고 이외의 경우 No를 출력하면 된다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin..

Problem Solving/BOJ 2023.04.17

제1회 와쿠(AGCU)컵 후기

제1회 와쿠(AGCU)컵 후기 대회https://www.acmicpc.net/contest/view/967 제1회 와쿠(AGCU)컵www.acmicpc.net 일시시작: 2023년 4월 16일 12:00 종료: 2023년 4월 16일 17:00 푼 문제A. 초코바간단한 사칙연산 문제 B. 사격 내기대회 때는 그냥 구현했는데 대회 끝나고 생각해 보니 xor 연산만 하면 되네? 점수가 2^n 꼴이므로 2진수로 나타내 둘 중 한 명만 1인 것만 점수로 추가해 주면 된다. C. 고양이는 많을수록 좋다처음에는 고양이를 생성하고 이후, 현재 고양이 수의 두배가 n보다 작으면 두 배 해주고 같거나 클 때는 n으로 만들어주면 된다. 연산의 총횟수를 출력.

후기/대회 2023.04.16

[백준 / BOJ] C++ 2041 숫자채우기

2041번: 숫자채우기 문제 https://www.acmicpc.net/problem/2041 2041번: 숫자채우기 N×M 크기의 격자에 적절히 수를 채우려 한다. 단, 인접한 수들의 차이로 1부터 (2NM-N-M)까지의 수가 한 번씩 나오도록 채우려 한다. N=2, M=2인 경우를 예로 들면 다음과 같은 방법이 있다. 위와 같 www.acmicpc.net 풀이 애드 혹 문제인 만큼 다양한 풀이가 있을 수 있다. 내 풀이는 가장 큰 차이부터 줄여나가면서 채우는 것이었다. 예시와 함께 보자. 3×3 크기의 배열이라고 하자. 그러면 1부터 12까지의 차이가 모두 존재해야 한다. 가장 먼저 1을 배치하고 큰 차이부터 채울 것이므로 13을 옆에 둔다. 그러면 배열은 아래와 같이 될 것이다. 1 13 ? ? ?..

Problem Solving/BOJ 2023.04.15
반응형