브루트 포스
-
백준 3085번 사탕게임 :: 마이구미카테고리 없음 2018. 3. 17. 22:52
이 글은 백준 알고리즘 3085번 "사탕 게임" 을 풀이한다.방법은 브루트 포스(노가다)를 통해 해결한다.문제 링크 - https://www.acmicpc.net/problem/3085 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오. 문제는 인접한 두 칸을 고른 후, 고른 칸을 서로 교환(swap)한 ..
-
백준 2858번 기숙사 바닥 :: 마이구미알고리즘 풀이/수학 2017. 9. 12. 20:32
이 글은 백준 알고리즘 문제 2858번 "기숙사 바닥" 을 풀이한다.문제 풀이는 수학적 접근과 브루트 포스를 활용한다.문제 링크 - https://www.acmicpc.net/problem/2858 상근이는 기숙사 생활을 한다. 상근이의 방의 크기는 L*W 이다.수업시간에 타일 채우기 경우의 수를 계산하던 상근이는 자신의 방도 1*1크기 타일로 채우려고 한다. 이 때, 가장자리는 빨간색으로, 나머지는 갈색으로 채우려고 한다.아래 그림은 상근이의 방의 크기가 4*3일 때 이다.어느날 상근이네 방에 하근이가 놀러왔다. 하근이는 아름다운 타일 배치에 감동받았다. 다시 방으로 돌아온 하근이는 빨간색과 갈색 타일의 개수는 기억했지만, 방의 크기는 기억해내지 못했다.빨간색과 갈색 타일의 개수가 주어졌을 때, 상근이..
-
백준 1107번 리모컨 [브루트 포스] :: 마이구미알고리즘 풀이/브루트 포스 2017. 5. 10. 23:12
이번 글은 백준 알고리즘 문제 1107번 "리모컨" 을 다뤄본다.문제 접근 방법은 브루트 포스. 즉, 노가다로 해결할 수 있다.1107번 리모컨 - https://www.acmicpc.net/problem/1107 리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 망가져있는지 주어졌을 때, N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 수빈이가 지금 보고 있는 채널은 100번이다. 본인은 처음에 단순히 채널을 한자리씩 분해하여..
-
백준 1038번 감소하는 수 :: 마이구미알고리즘 풀이/브루트 포스 2017. 4. 20. 00:17
이번 글은 백준 알고리즘 1038번 문제 "감소하는 수" 를 다뤄본다.문제는 동적계획법으로 접근해야한다. 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다. 하지만 본인은 도저히 동적계획법으로는 생각나지 않아, 브루트 포스(노가다)로 풀었다.완전한 노가다는 아니라, 불필요한 과정을 제외시킴으로써, 시간 제한을 피할 수 있었다.테스트케이스가 많은 것도 아니고, 노가다로 풀어도 충분히 시간 제한에 걸리지 않을 거..