지구정복

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net -문제해설 처음에 dfs로 풀다가 머리가 깨질뻔했다... 욕나오고; 어떻게하면 풀 수는 있을 것 같은데 아직 내 실력이 부족한 것 같다 ㅎ 일단 이 문제를 통해서 최적의 해를 구하는 문제가 나오면 일단은 탐색방법으로 접근을 하고 탐색방법중에서 가능한 방법을 먼저 적용해야겠다는 노하우가 생겼다. 완전탐색이나 이분탐색 등의 방법을 생각하면 될 것 같다. 1. n,m을 입력받는데 m이 ..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net -문제해설 이제부터 그래프가 나오면 웬만해서는 dfs, bfs풀이를 먼저 생각해야 겠다. 이 문제는 dfs를 이용하면 쉽게 풀 수 있는 문제이고 방문여부와 깊이를 잘 조정하면 각 도형에 대한 숫자 합을 구할 수 있다. 먼저 dfs를 이용해서 아래 도형들을 구해준다. 그리고 ㅗ 도형에 대해서는 따로 구해주면 된다. 1. n, m 입력받고 그래프 저장할 arr, 방문여부배열 visit 선언 2. ar..

https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net -문제해설 처음에는 단순히 반복문 돌리면서 변수 a, b 선언하고 1씩증가하다가 a, b가 x, y와 같아지면 정답을 출력하는 식으로 짰는데 시간초과가 나왔다. 그래서 일일이 일단 다 써보니 규칙을 알아냈다. 예를 들어 5 6 1 4를 구한다고 해보자. 1 - 1, 1 여기 2 - 2, 2 3 - 3, 3 4 - 4, 4 5 - 5, 5 6 - 1, 6 여기 7 - 2, 1 8 - 3, 2 9 - 4..

https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net -문제해설 9이하이면 1자리 99이하이면 2자리 999이하이면 3자리 ... 이므로 i가 1부터 입력값인 n까지 반복문을 돌면서 i가 10일 때, i가 100일 때, i가 1000일 때.... 더해지는 수 tmp를 1씩 증가시킨다. 그리고 ans에 누적해서 더한다. ans += tmp; 파이썬의 경우 규칙을 이용해서 풀었다. 예를 들어 n이 1002일 경우 1~9까지의 합은 9 10~99까지의 합은 180 100~999까지의 합은 2700 여기서 규칙을 확인해보면 1~9 : 9 * 1 * 10^0 10~99 : 9 *..