백준 문제풀이

16953번: A → B (acmicpc.net)  매우 간단한 문제이다. 자주 써왔던 케이스 분류와 재귀를 쓰면 쉽게 풀릴 것이라는 생각을 했고, 그대로 코드를 썼더니 그냥 맞혔다.  그나마 사용된 슥삭 프로그래밍이라고는 곱하기 2는 그냥 비트연산자 "  긴 말 필요없이 코드를 보면 이해가 갈 것이다. 그냥 재귀로 돌면서 1을 더해준 것과 2를 곱해준 두 가지 경우의 수로 계속 가지를 치면서 나가주면 된다. #include #include using namespace std;long long int first, latter;long long int tryCount = -1;void checkPossiblethings(long long int num, long long int cnt){ if (nu..

15666번: N과 M (12) (acmicpc.net)  N과 M 시리즈를 쭉 풀다 보면 그래도 몸이 익어 금방 풀 수 있는 문제이다.  우선 비내림차순을 만족하는 경우, 백트래킹 알고리즘을 사용하기 보단 일반적인 재귀 방식으로 푸는 것이 깔끔하다.  그냥 해당 원소를 내가 접근하여 "골랐는지 안골랐는지"만 생각해서 골라주면 되는 것이다.  아래에 이와 아예 같은 로직을 사용하는 백준 문제에 대한 해결 포스팅을 첨부하니 아래 글을 참고하면 좋을 듯 하다.백준 15652 - N과M (4) [C/C++] — 예비 대학원생의 Computer Science 저장소 (tistory.com) 백준 15652 - N과M (4) [C/C++]https://www.acmicpc.net/problem/15652  중복을..

https://www.acmicpc.net/problem/15663  반성해야 하는 문제.. 쉬운 개념을 생각치 못하고 뱅뱅 돌다가 결국 시간을 많이 쓰고 해결했다...  N과 M 시리즈 중 어려운 문제인 것 같고, 중복 수열의 출력을 피해야 하기 때문에 이를 어떻게 처리해주어야 할지 고민해주어야 한다.  우선 백트래킹 알고리즘을 사용하여 인덱스 접근을 매번 새롭게 해주어야 하는 것은 이전의 N과 M 시리즈 문제 중에 비슷한 게 있었기 때문에 쉽게 떠올릴 수 있었다.  문제는 중복 수열의 출력을 어떻게 피할 것이냐는 것... 생각보다 수학적으로 생각해보면 간단하게 피할 수 있었다.  아무리 길이가 긴 수열이더라도, 그 특징 상 마지막 수만 다르다면 다른 수열이 되는 것에 주목해야 한다.배열에 값들을 입력..

https://www.acmicpc.net/problem/11053  DP 문제들을 본격적으로 풀기 전 머리 풀기로 풀어볼만한 문제라고 생각한다.  주어진 갯수만큼의 원소를 가지는 수열이 주어진 경우, 단순 증가 수열의 최대 크기가 얼마겠느냐라고 묻는 문제이다.  먼저 가져야 하는 생각은, 이전의 내가 확인했던 최대 단순 증가 수열의 크기를 다음 인덱스에 접근했을 때 써먹을 수 없을까? 라는 생각이다.  간단히 이야기 해보자면, 1 2 3 2 3 라는 수열이 생각해보자.첫 번째 1에 접근한 경우 당연히 최대 수열의 크기는 1이다.두 번째 2에 접근한 경우, 2 가지 경우가 있다.첫 번째 1을 무시하고 2를 단순 증가 수열의 첫 번째 원소라고 생각한 경우이 경우 최대 단순 증가 수열의 크기는 1이다. (2..