Doby's Lab

종종 BFS나 DP를 풀 때 2차원 배열이라는 키워드를 고려하면 쉽게 풀리는 경우가 있다. 꼭 행과 열의 의미가 아니라 각각 행의 의미와 열의 의미를 다르게 주어 풀 수 있다. 2차원 배열이라는 키워드 꼭 리마인드 하기

https://www.acmicpc.net/problem/1850 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 이번 문제는 TC를 통해 규칙을 파악했다. TC #1 3 4 TC #2 3 6 TC #3 500000000000000000 500000000000000002 분명 주어진 입력값만큼 1의 개수라는 말인데 어째서인지 입력값끼리의 최대공약수도 똑같다는 것을 발견했다. TC #2를 보면 3 6으로 111과 111111의 최대공약수를 구하는 것이다. 물론 111*1001 = 11111..

https://www.acmicpc.net/problem/13423 13423번: Three Dots 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 다음 줄부터 차례로 T개의 테스트 케이스가 주어진다. 각각의 테스트 케이스의 첫째 줄에 점의 개수 N(3 ≤ N ≤ 1,000)이 주어 www.acmicpc.net 이 문제는 3가지 점 모두 브루트 포스로 구하면 시간 초과가 난다. Worst Case: O(n^3) => O(1000^3) 솔루션 두 점까지는 브루트 포스로 구하고, 나머지 한 점은 2번째 점과 1번째 점의 차이를 만족하도록 고르는 점과 2번째 점의 차이가 같은 점을 이분 탐색으로 구해주었다. >> 이분 탐색을 위해 입력받은 점들을 정렬해주었다. #include #incl..

https://www.acmicpc.net/problem/11005 11005번: 진법 변환 2 10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net 1. 주어진 N을 B로 나머지 연산 후 그 값을 'B진법'으로 바꾼다. 2. B진법으로 바꾼 값을 결과 문자열에 더한다. 3. 다음 값을 위해 N을 B로 나눠준다. 4. 1~3번 과정이 끝나면 결과 문자열을 뒤집는다. #include #include #include using namespace std; char change(int value) { if (value > N >> B; strin..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 노트에 구현을 해보았다. 시작 수가 0이면 안 되기 때문에 1 ~ 9까지 수들을 각 수로부터 파생될 수 있는 수들을 트리 형식으로 그려볼 수 있었다. 다음과 같은 특징을 지니고 있었다. 시작 수는 0이 될 수 없다. 1 ~ 8까지는 두 가지의 수가 파생될 수 있다. 0과 9는 각각 1, 8 밖에 파생시키지 못한다. 이러한 관계식을 어떻게 나타낼 수 있을까 한참을 고민하다가 2차원 배열을 떠올렸다. cache[i번째 자리][숫자 j] = 숫자 j가 나온 횟수; 다음 계단식의 특징을 가지고서 점화식을 나타내면 //..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 여전히 DP 문제는 접근하기 어렵다. 문제를 풀 때마다 '이렇게 생각해보자'라는 지난 DP 문제로부터 나름대로 얻은 팁을 적용해봐도 어렵다. 이제까지 접근했던 방식들을 떠올려보면 직접 TC를 가지고서 output을 노트에 도출하며 관계성과 점화식을 세웠었다. [input] 6 6 10 13 9 8 1 [answer] 33 맨 처음에는 조금 멍청하게 접근을 했는데 n번째 포도주를 선택한다고 했을 때,..

현재 값을 중심으로 생각 (점화식 세울 때 까다로워짐) 일부분을 캐치하는 능력 (연속 3번은 안 된다 했을 때, '0번, 1번, 2번 연속을 알아봐야겠다'라고 생각이 드는 능력) 점진적으로 문제를 해결할 수 있다는 걸 항상 암시하기 어떠한 조건들을 따져야 할지 캐치하는 능력 DP를 훌륭하게 푸는 법 (https://debuglog.tistory.com/80)

https://www.acmicpc.net/problem/23628 23628번: 악마의 연차 계산기 360일 일하면, 휴가를 받아야 함이 마땅하다. 그에 따라, 우리 회사도 연차와 월차를 주고자 한다. 연차와 월차는 사용하면 하루 쉴 수 있는 것이다. 그런데, 인력이 너무 부족한 탓에 그만…. 지 www.acmicpc.net 처음엔 많은 조건 분기로 풀었으나 이는 너무 복잡한 코드였다. #include using namespace std; int main() { int y, m, d; int dy, dm, dd; cin >> y >> m >> d; cin >> dy >> dm >> dd; int year = 0; int month = 0; int days = 0; if (dy == y) { if (dm..