나그네

17291번: 새끼치기 문제 https://www.acmicpc.net/problem/17291 17291번: 새끼치기 실험실에서 새로운 종의 벌레 한 마리가 탄생하였다. 벌레는 스스로 분열하며, 분열하면 자기 자신과 같은 벌레를 한 마리 만들어 내게 된다. 벌레가 분열하는 규칙은 다음과 같다. 벌레는 기준 www.acmicpc.net 풀이 1년에는 1마리, 2년에는 2마리, 3년에는 4마리, 4년에는 8마리가 되었다가 1년에 탄생한 1마리가 죽어 7마리가 된다. 계속해보면 5년에는 14마리가 되고, 6년에는 28마리가 되었다가 2년에 탄생한 1마리와 3년에 탄생한 2마리가 죽어 25마리가 된다. 여기서 홀수년에 탄생한 개체는 3번 분열 후, 짝수년에 탄생한 개체는 4번 분열 후 사망하기 때문에 반드시 ..

Round #874 (Div. 3) 대회 https://codeforces.com/contest/1833 Dashboard - Codeforces Round 874 (Div. 3) - Codeforces codeforces.com 푼 문제 A. Musical Puzzle 입력받은 문자열에서 연속된 두 글자의 종류의 수를 출력하면 된다. 중복되는 부분 문자열 처리를 위해 map 자료구조를 사용했다. #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { string s; int n; cin >> n >> s; map M; for (int i = 0; i < n - ..

18186번: 라면 사기 (Large) 문제 https://www.acmicpc.net/problem/18186 18186번: 라면 사기 (Large) 라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i www.acmicpc.net 풀이 [백준 / BOJ] 18185 라면 사기 (Small) 문제 / [백준 / BOJ] 18185 라면 사기 (Small) 풀이 위 문제를 먼저 풀고 난 후 풀면 비교적 쉽게 풀 수 있다. 위 문제와의 차이점은 1군데, 2군데, 3군데 구매했을 때 가격이 3, 5, 7이 아니라 b, b+c, b+2*c 라는 것이다. 즉, 위 문제는 ..

18185번: 라면 사기 (Small) 문제 https://www.acmicpc.net/problem/18185 18185번: 라면 사기 (Small) 라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i www.acmicpc.net 풀이 처음에는 앞에서부터 최대한 많이 3군데 연속해서 구매하고, 다시 앞에서부터 2군데, 그리고 낱개를 구매하도록 했으나 WA를 받았다. 2~3시간 정도 고민하다가 질문 게시판에서 반례 테스트 케이스를 얻어 2시간 정도 더 고민하고서야 풀었다. 0번 공장부터 차례대로 방문하며 아래 과정을 거친다. 1. i, i+1, i+2번째 공장에서..

10988번: 팰린드롬인지 확인하기 문제 https://www.acmicpc.net/problem/10988 10988번: 팰린드롬인지 확인하기 첫째 줄에 단어가 주어진다. 단어의 길이는 1보다 크거나 같고, 100보다 작거나 같으며, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 풀이 먼저 문자열을 입력받고 이를 복사한다. 복사한 문자열을 헤더파일의 reverse 함수를 사용해 뒤집어준다. 그리고 원본과 뒤집힌 복사본의 일치 여부를 출력한다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); string a, b; cin >> a; b = a; reverse(b.begin(), b.end(..

15786번: Send me the money 문제 https://www.acmicpc.net/problem/15786 15786번: Send me the money 입력의 첫째 줄에 석규가 기억하는 원본 알파벳의 수 N(1 ≤ N ≤ 100)과 포스트잇의 개수 M(1 ≤ M ≤ 1000)이 주어진다. 다음 줄에 길이가 N인 알파벳 대문자로 이루어진 문자열 S가 주어진다. 이 후 M www.acmicpc.net 풀이 기억하는 원본 알파벳의 각 글자가 순서대로 있는지 포스트잇의 문자열에서 찾으면 된다. 문자열의 find 메소드로 원본의 0번 index의 글자를 포스트잇의 처음부터 찾고 존재한다면 그 위치 + 1부터 1번 index의 글자를 찾으며 반복한다. 중간에 찾을 수 없다면 flag를 1로 바꾸고 멈..

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

16507번: 어두운 건 무서워 문제 https://www.acmicpc.net/problem/16507 16507번: 어두운 건 무서워 첫 번째 줄에는 사진의 크기를 의미하는 정수 R, C (1 ≤ R, C ≤ 1,000)와 사진 일부분의 밝기 평균을 알아볼 개수를 의미하는 정수 Q (1 ≤ Q ≤ 10,000)가 주어진다. 다음 R개의 줄에 걸쳐 R×C 크기의 사 www.acmicpc.net 풀이 [백준 / BOJ] C++ 11660 구간 합 구하기 5와 같은 문제다. [백준 / BOJ] C++ 11660 구간 합 구하기 5 11660번: 구간 합 구하기 5 문제 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해..

28014번: 첨탑 밀어서 부수기 문제 https://www.acmicpc.net/problem/28014 28014번: 첨탑 밀어서 부수기 첫째 줄에 첨탑의 개수 $N$이 주어진다. $(1\leq N\leq 5\,000\,000)$ 둘째 줄에는 앞에서부터 차례대로 첨탑의 높이 $H_1, H_2, \cdots, H_n (1\leq H_i\leq 1\,000\,000)$ 이 주어진다. 입력으로 주어지는 모든 수는 정 www.acmicpc.net 풀이 밀려 넘어지는 첨탑의 높이가 바로 그다음 첨탑의 높이보다 클 때만 그다음 첨탑도 밀려 넘어진다는 것은 밀려 넘어지는 첨탑의 높이가 바로 그다음 첨탑의 높이보다 작거나 같을 때 다음 첨탑을 밀어야 한다. 즉, i번째 첨탑과 i+1번째 첨탑의 높이를 비교해 i+1..

2583번: 영역 구하기 문제 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 풀이 모눈종이 위의 몇 가지 직사각형을 제외한 공간의 수와 각각의 넓이를 오름차순으로 출력하는 문제다. 먼저 2차원 배열을 만들고 직사각형을 채워야 하는데 입력은 모눈종이의 좌표로 입력되는 반면 배열의 인덱스와 맞추기 위해서 2중 for문을 사용해 (x1, y1)부터 (x2, y2)까지 -1로 색칠을 해준다. 배열이 -1이 아닌 공간에 대해 bfs..