지구정복

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 *..

https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net -문제해설 처음에 c, p, z, y 변수를 만들어서 연속되면 각 변수를 1씩 증가시키고 새로운 변수가 나오면 새로운 변수값을 1씩 증가시켰는데 이럴 필요가 없었다. 그냥 우측 혹은 아래측 문자가 현재 문자와 같으면 cnt 변수를 1씩증가시키고 max 값과 비교, 같지 않다면 cnt를 1로 초기화시키고 max값과 비교하는 식으로 풀면 되는 문제였다. 1. n을 입력받고 문자열 입력받은 뒤 .charAt()으로 문자로 나눠서 chu배열에 저장 2. 먼저 각 행에 대해서 우측사탕과 교환하고 최대값 구하는 과정을 반복한..