나그네

27972번: 악보는 거들 뿐 문제 https://www.acmicpc.net/problem/27972 27972번: 악보는 거들 뿐 키위새는 피아노를 잘 치고 싶었지만 악보를 볼 줄 몰랐다. 그러다 동영상 사이트에서 수열만 보고 피아노를 연주하는 동영상을 찾아냈다! 하지만 동영상에서 보여주는 수에 맞는 음을 누르자 www.acmicpc.net 풀이 음의 높낮이가 변하면 수를 1씩 늘리고 줄이기만 하므로 가장 긴 연속된 증가/감소하는 부분 수열의 길이가 정답이 된다. 연속이 끊길 때 길이 초기화를 1로 해야 함에 주의하자. 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int m, a = 1, b = 1..

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

27969번: I LOVE JavaScript 문제 https://www.acmicpc.net/problem/27969 27969번: I LOVE JavaScript 한 줄에 걸쳐, ASON 객체의 유효한 표기가 주어진다. 주어지는 문자열의 길이는 스페이스 문자를 제외하고 $15\,000$ 이하이다. www.acmicpc.net 풀이 ASON을 구성하는 것은 [, ], 문자열, 정수가 있고 각각 공백으로 구분되어 있으므로 각각을 토큰화하기 위해 while문 조건 안에 cin을 넣어 EOF가 발생할 때까지 공백을 기준으로 문자열을 입력받는다. 스택을 사용해 객체의 시작을 의미하는 [가 입력되면 0을 push한다.push 한다. 마찬가지로 정수가 입력되면 8을, 문자열이 들어오면 길이+12를 push 한다...

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 함수로 최초로 같거나 큰 수의 사탕이 있..

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

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

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

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

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