Doby's Lab

https://www.acmicpc.net/problem/14562 14562번: 태권왕 첫째 줄에 테스트 케이스의 수 C(1 ≤ C ≤ 100)이 주어진다. 둘째 줄부터 C줄에 걸쳐 테스트 케이스별로 현재 점수 S와 T가 공백을 사이에 두고 주어진다. (1 ≤ S < T ≤ 100) www.acmicpc.net 이번 문제를 풀면서 저번에 포스팅했던 리모컨 문제가 떠올랐었다. (https://draw-code-boy.tistory.com/99) 솔루션 간단한 BFS 문제였다. S와 T의 점수가 주어지면 두 가지 방법으로 S의 점수를 올려준다. S의 점수가 2배가 된다. 단, T의 점수에는 3점이 추가된다. S의 점수에 1점이 추가된다. 두 가지 경로를 가지고 BFS를 짜주면 된다. 단, 이번 문제에서 주..

https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 이번 문제는 (https://jaimemin.tistory.com/682)을 참고한다. 개념 학생 때 배웠던 nCr 개념이 등장한다. 정확히는 n Combination r이라고 부른다. 이와 같이 따라오는 게 nPr로 이는 n Permutation r이라고 부른다. 이 둘은 조합론으로 둘 다 공식이 존재한다. 솔루션 1 (실패) 이 공식을 활용하여 두 개의 팩토리얼 함수를 구현하여 풀려고 했다. [조금 다른 방식의 팩토리얼 함수] 각각 n!, (n - r)!, r! 은 시간이 오래 걸릴뿐더러 숫자까지 너무 커질 ..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 이번 문제는 TC를 보고 나서 점화식을 어떻게 짜야할지 혼란을 가져다주는 문제였다. 하지만, TC를 간단하게 생각해보면 쉽게 풀 수 있었다. 솔루션에 도달하는 과정 5 50 10 100 20 40 30 50 70 10 60 다음 TC가 문제를 다시 생각해보게 했었다. 그 전의 코드는 이렇다. #include #include using namespace std; int T; int cac..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 이번 문제는 어떠한 논리라기보다 너무 복잡한 생각을 필요하지 않은 문제다. 오히려 간단해지기 위해 복잡한 생각을 해야 했던 문제(?)였다. 처음에는 어떻게 최솟값을 도출할지를 생각하는 과정에서 두 가지로 나뉘었다. 한 번에 최솟값을 도출하는 방법(?) 모든 채널을 대입해보면서 최솟값을 찾는 방법 1번 방법은 생각만 해도 반례가 너무 많을 거 같았다. 주어진 수가 500,000이라면..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 처음 문제를 봤을 때는 행과 열이 둘 다 100,001인 bool 2차원 배열을 선언해서 두 노드가 주어지면 간선을 1로 바꿔주어서 각 행을 DFS를 돌리면 될 거라고 생각했다. 하지만, 이럴 경우 배열의 크기가 너무 커서 오류가 나게 된다. 여기서 알아냈던 게 vector의 2차원 동적 기능(?)이었다. 기존 1차원 vector배열에서 push_back을 이용하는 것은 늘 사용했지만 2차원에서 사용할 방법은 생각도 못 해봤다. 각 행에 push가 가능하다는 ..

https://www.acmicpc.net/problem/11561 11561번: 징검다리 각 테스트 케이스마다 한 줄에 승택이가 밟을 수 있는 최대 징검다리 수를 출력한다. www.acmicpc.net 이번 문제는 수학 카테고리에 넣고 싶었으나 그래도 문제의 베이스는 이분 탐색이라서 이 카테고리에 넣어둔다. 점프를 최대로 하려면 1칸 점프를 한 뒤, +1 점프, +1 점프로 목적지에 도달해야 최댓값이 도출될 수 있다. 하지만, 100칸이 있을 때는 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 + 13 + 14까지 더하면 100이 넘는다. 그래서 이럴 경우에는 13번째 점프를 할 때, 100을 채우게끔 22칸을 뛰어주면 된다. 즉, 코드로 구현을 할 때는 val..

https://www.acmicpc.net/problem/6443 6443번: 애너그램 첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램의 수가 100,000개 이하인 단어만 입력으로 주 www.acmicpc.net 단순한 백트래킹 문제인 줄 알았으나 꽤 조건이 까다로운 문제다. 허나, 이 조건은 예전에 N과 M 시리즈를 풀 때도 한 번 크게 겪었던 똑같은 유형이었다. (N과 M (9) 문제: https://www.acmicpc.net/problem/15663) (N과 M (9) 포스팅: https://draw-code-boy.tistory.com/29) 이 문제에서 필요한 건 정렬과 이전 노드(같은 d..

https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 이분 탐색이라는 문제를 알고서 풀었기 때문에 어느 타이밍에 이분 탐색이 나와야 할지 감을 잡지 못했다. 첫 번째로 떠오른 방법은 1) 입력을 받을 때, 종유석과 석순으로 나누어서 석순이면 밑에서부터 장애물이 하나씩 추가되는 것이기 때문에 1 ~ 입력값까지 +1을 해주고, 종유석이면 위에서부터 밑으로 +1을 해주었다. 2) 각 구간 별로 부숴야 할 장애물들이 저장되어있기 때문에 정렬을 하고, 맨 앞에 ..