문제 16953번: A → B 첫째 줄에 A, B (1 ≤ A A*2 2. 1을 수의 가장 오른쪽에 추가한다 -> A*10 +1 위의 두 연산을 DFS 형태로 재귀적으로 부르면 브루트포스 방식으로 해결 가능하다. 간단하게 풀렸을것 같지만, 처음 시도했을때 틀렸습니다를 받았다. 뭐가 문제일까 고민하다가, 변수의 타입을 int로 한게 문제였음을 깨달았다. dfs() 함수에서 if(num > B) return; 이라는 코드가 있는데, 만약 num*2를 계속해서 하다가 int의 범위를 벗어나면 이 부분이 문제가 발생할 수 있다. 따라서 int를 long 타입으로 바..
문제 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 풀이 이 문제의 풀이를 요약하자면 아래와 같다. 1. 왼쪽, 오른쪽 번갈아서 미네랄 파괴 2. 미네랄 파괴 후 공중에 떠있는 클러스터 BFS로 찾기 3. 공중에 떠있는 클러스터들을 아래로 내리기 먼저, 1번을 구현하는 것은 쉽다. 단순히 홀수, 짝수를 나누어 왼쪽에서부터 탐색, 오른쪽에서부터 탐색해서 'x'를 '.'으로 바꿔주기만 하면 된다. 2번을 구현하는 것은 조금 까다롭다. 우선 '공중에 떠있다'라는 것은 클러스터가 땅에 붙어있지 않다는 것을 의미한다. 이것은 BF..
문제 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net 풀이 1. N, M이 50 이하로 작다. 2. 꼭짓점을 살펴보기 위해서는 기준점에서 3군데만 찾아보면 된다. 3. N과 M중 더 작은 수가 정사각형의 최대길이다. 4. 따라서 최대 50(N)*50(M)*3(꼭짓점 3개 비교)*50(정사각형의 최대 길이) 번의 연산이 필요하므로 브루트포스 방식이 가능하다! 풀이법은 간단하다. 정사각형의 최대 길이는 N과 M 중 더 작은 것일 것이다. 이것을 len이라고 하자. 매번 모든 원소를 조사할 필요 없이 세로는 N-l..