나그네

28701번: 세제곱의 합 문제 https://www.acmicpc.net/problem/28701 28701번: 세제곱의 합 $a$의 제곱은 $a$를 두 번 곱한 수로, $a^2$으로 표현합니다. $a^2 = a \times a$입니다. 또한, $a$의 세제곱은 $a$를 세 번 곱한 수로, $a^3$으로 표현합니다. $a^3 = a \times a \times a$ 입니다. www.acmicpc.net 풀이 주어진 대로 수식을 출력하면 된다. pow 함수는 return value가 double이기 때문에 type 변환을 꼭 해줘야 한다. 혹은 변수에 저장한 다음 출력해야 한다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(0);..

27965번: N결수 문제 https://www.acmicpc.net/problem/27965 27965번: N결수 $10$진법 상에서 양의 정수 $1$, $2$, $3$, $\cdots$, $N$을 이어 붙여 만든 수 $\overline{123\cdots N}$을 $N$결수라고 한다. 예를 들어 $12345$는 $5$결수이고, $12345678910111213$은 $13$결수이다. $N$과 정수 $K$가 주어 www.acmicpc.net 풀이 N결수를 만들고 K로 나누기엔 N결수가 너무 큰 수가 되기 때문에 long long의 범위를 벗어나게 된다. 따라서 과정을 쪼개 중간중간에 나머지 연산을 해야한다. N = 5, K = 7인 경우를 예로 들면, 1~5를 차례대로 나열해야한다. 이때 1을 K로 나눈 ..

11966번: 2의 제곱인가? 문제 https://www.acmicpc.net/problem/11966 11966번: 2의 제곱인가? 자연수 N이 주어졌을 때, 2의 제곱수면 1을 아니면 0을 출력하는 프로그램을 작성하시오. www.acmicpc.net 풀이 2의 제곱수면 log2를 씌웠을 때 정수가 나올 것이다. 따라서 log2(n)이 정수이면 1, 아니면 0을 출력하면 된다. log2의 return 값은 double 형태이다. 원래 수에서 int로 형변환한 값을 뺀 값이 0이면 log2(n)은 정수이다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; cout

19568번: 직사각형 문제 https://www.acmicpc.net/problem/19568 19568번: 직사각형 당신이 만든 표에 적힌 수를 한 줄에 30개씩, 30줄로 출력하여라. 정확한 형식은 예제 출력을 참고하자. www.acmicpc.net 풀이 2차원 약 팔기다. 아직 약 팔기 문제를 풀지 않았다면 아래 문제를 풀어보고 오는 것을 추천한다. [15311 약 팔기 문제] [15311 약 팔기 풀이] 힌트 더보기 약 팔기 문제처럼 진수를 이용한다. 풀이 더보기 30×30 배열을 사용하므로 중간인 15를 기준으로 삼아 15진수를 사용한다. 중심을 기준으로 좌우로 1, 15를 채우고 상하로 15^2, 15^3을 채운다. 나머지 칸은 모두 0으로 채우면 50000을 조금 상회하는 수까지 나타낼 수..

27970번: OX 문제 https://www.acmicpc.net/problem/27970 27970번: OX O와 X로 이루어진 문자열이 주어진다. 모든 문자를 X로 만들 때까지 다음 연산을 반복할 때, 시행하는 연산의 횟수를 구하시오. 문자열의 가장 왼쪽에 있는 O를 X로 바꾸고, 그보다 왼쪽에 있는 X www.acmicpc.net 풀이 i번째 인덱스에 O가 있으면 이 O를 X로 바꾸기 위해서는 2^i번 연산을 수행해야 한다. O가 있는 인덱스 i에 대해 2^i의 합을 출력하면 된다. int 범위를 벗어날 수 있으므로 long long을 쓰고 모듈러 연산을 계속 해줘야 한다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(0)..

15311번: 약 팔기 문제 https://www.acmicpc.net/problem/15311 15311번: 약 팔기 첫 번째 줄에 동규의 최대 약 요구량을 나타내는 정수 N ($=1\, 000\, 000$) 이 주어진다. www.acmicpc.net 풀이 친구의 추천으로 며칠간 고민하다가 갑자기 풀이가 떠올랐다. 1부터 1,000,000까지 모두 나타낼 수 있어야 하는데, 1,000,000 = 1,000 * 1,000이고 배열의 최대 크기 2,000 = 2 * 1,000이다. 그래서 1000을 1000개 넣고 나머지 1000칸에 모두 1을 넣으면 1부터 1,000,000까지 만들 수 있다. 코드 #include using namespace std; int main() { ios::sync_with_s..

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 계..

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); ..

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의 제곱승 꼴로 증가..

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; ..