2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 과정 처음에는 그래프인가 했다가 이것도 계단 오르는 규칙이 있는 문제이므로 DP를 이용해서 풀어보려고 했다. 계단을 오르는데는 2가지 규칙이 있다. 1. 연속된 2개 계단 오르기 2. 한 칸만 건너뛰기 즉, 현재 내가 서있는 칸(N)을 연속된 2번째 계단으로 만들건지,(N-1을 밟은 상태) 한칸 건너뛴 계단으로 만들건지(N-1을 안밟은 상태) 결정해야 한다. 따라서, DP[N] = max(DP[N-3] + Arr[N-1] + Arr[N], DP[N-2] + Arr[N]) 또..

1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 과정 백준 2839처럼 한 숫자에 대해 지지고 볶아서 최소한으로 원하는 결과를 만드는 유형으로 파악했다. 즉, 마지막 수는 2를 만들어서 1로 빼주는 과정으로 진행되어야 한다. #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int N = 0; // 정수 N int count = 0; // 최종적으로 N을 1로 만드는데 연산한 횟수 cin >> N; while (N != 1) // 최종적으로 2를 만들어야하기때문 { // N이 3으로 나누어 떨어지는 경우 if (N % 3 =..

1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 과정 가로 세로로 지렁이가 움직일 수 있는 영역을 묶음으로 처리해야겠다고 생각했다. 처음에는 벡터에 배추가 심어진 좌표값을 하나씩 받고, 그것들의 평균치를 구해서 평균값에 들어오면 같은 묶음, 아니면 다른 묶음으로 처리하려고 했다. 하지만, 2*3마냥 진짜 무더기로 있는 경우 평균값을 어떻게 구해야할 지 몰랐고, 추가적으로 문제를 잘못이해한 내용이 있다. 무조건 동서남북으로 5개까지만 이동 가능한 줄 알았는데, 계속 쭉 이동할 수 있었다. 결국 답을 찾아본 결과 DFS와 B..

11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 과정 정렬과 좌표를 보자마자 "sort"를 x좌표, y좌표에 대해 각각 1번씩 총 2번을 써야하나? 생각했다. 근데 기억하기론, sort(시작, 끝, 함수명)이었던걸로 기억하고, bool형 비교함수를 통해 T/F로 2개의 원소를 비교하여 오름차순으로 정리한다. 근데, 저번과 마찬가지로 sort쓰기 싫었다.(그냥 고집) 않이 sort쓸수 있는지 없는지를 공부할 필요는 없잖아? 그래서, 언리얼C++에서 배웠던 mu..

10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 과정 이 문제 보자마자 '저번 정렬 문제때 생각한 아이디어를 쓸 수 있겠다' 라는 생각이 들었다. 왜냐하면, 이 문제는 1. 주어지는 수들이 모두 자연수 2. 중복이 가능한 문제 조건 을 가지고 있기 때문이다. 즉, 부여되는 숫자를 인덱스로 가지는 벡터값을 +1씩 올려서 출력한다. 코드 #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N =..

2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 과정 N은 3 * a + 5 * b로 이루어진 수이다. 가장 적은 봉지를 들고 가고 싶다고 했으니까, 5kg봉지를 최대한 들고, 남은 양을 3kg봉지로 채워야 한다. 음... 그럼 예를 들어서 15kg이 있으면, 5로 미리 나눠보면 이게 3봉지만 필요하다는게 바로 나오니까? N을 5로 먼저 나눠보고, 안나눠지면 -3해서 3kg봉지 1개 만들고 이런식으로 하면 될거같다. (모래성 깃발놀이 할 때 처음에는 크게크게 가져가다가 갈수록 적게 가져가는 것처럼) → 정답 찾아보니 이..

2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 핵심 가장 먼저 든 생각 : 범위가 커서 시간초과가 날거같다. → 저번에 쓴 https://ssin-estella.tistory.com/28 관련 방법 사용해야지 두번째로 든 생각 : (sort()는 안써본다는 고집)아니, 중간에 요소를 넣어야한다고?? 이거 연결리스트 써야겠는걸? → 이게 문제가 되었다.. 일단 연결리스트로 중간삽입을 쉽게 하겠다는 발상은 좋았을지 모르지만, 1개만 기억하는 금붕어덕분에 1시간을 날렸다. 연결리스트는 중간삽입은 유용하..

2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌 www.acmicpc.net 핵심 이런 문제는 대놓고 "나 숫자에 패턴있어요" 하는 문제라.. 패턴을 찾는게 중요하다. 그렇게 어려운 패턴은 아니지만, 눈으로 봤을 때는 잘 안보여서 적으면서 찾았다. (에키드나를 그렇게 했는데;; 육각형 아직도 안보이다니. 레이드 더해야겠는걸?) 위처럼 패턴을 찾아서 점화식을 만들었다. #include using namespace std; int main() { int num = 0; int layer = 1; cin >> num; if (num == 1) laye..

15552번: 빠른 A+B첫 줄에 테스트케이스의 개수 T가 주어진다. T는 최대 1,000,000이다. 다음 T줄에는 각각 두 정수 A와 B가 주어진다. A와 B는 1 이상, 1,000 이하이다.www.acmicpc.net문제자체는 A+B를 출력하지만 하면 되는 단순한 문제이지만, 빠른 입출력이라니? 했다. cin, cout기본적으로 C++에서는 cin과 cout으로 입출력을 한다. 근데 문제에서는라고 친절하게 알려준다. cin.tie(NULL)이거 보자마자 든 생각 : C++은 nullptr아닌가? (맞다 nullptr가능) 기본적으로 입력과 출력은 연결되어있다. 즉, cin과 cout 스트림이 서로 연결되어있는데 이게 빠른 입출력이 필요한 상황에서 문제가 된다. 왜냐하면, cin과 cout처럼 엮여있..

1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 핵심 소수찾기 관련 시간복잡도는 O(n), O(√n)처럼 다양한데, 그중에서 바로 생각이 안났던 에라토스테네스의 체 알고리즘으로 풀었다. 에라토스테네스의 체 에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 에라토스테네스의 체 수학에서 에라토스테네스의 체는 소수를 찾는 빠르고 쉬운 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 알고리즘[편집] ko.wikipedia.org 이건 거의 O(NloglogN)..? 인가 하여튼 빠르다. 이 문제를 풀면서 헷갈렸던게, 결국 에라토스테네스..