나그네

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

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을 조금 상회하는 수까지 나타낼 수..

11441번: 합 구하기 문제 https://www.acmicpc.net/problem/11441 11441번: 합 구하기 첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 www.acmicpc.net 풀이 최대 10만 개의 연속된 수의 합을 구해야 한다. 따라서 입력과 동시에 모든 구간 합을 구할 수 있도록 구현이 가능한 누적 합 배열을 만들어 해결할 수 있다. 누적 합 알고리즘은 수열의 합 Sn에 대해 Sn - Sm-1 이 Am ~ An까지의 합과 같음을 이용하는 알고리즘이다. 코드 #inc..