Brute Force

[문제] https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net [코드] import sys if __name__ == '__main__': target = int(sys.stdin.readline().strip()) m = int(sys.stdin.readline()) if m: # 고장난 버튼이 있을 경우 broken = set(sys.stdin.readline().split()) else: broken = set() ans = a..

[문제] https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net [풀이] 처음에는 슬라이싱을 이용해 str(i)[-3:] == '666' 이런 식으로 끝에서부터 세 자리씩 '666'과 같은지 비교해야 되나 했다. 생각해보니 문자열은 in을 이용해 간단하게 풀 수 있는 방법이 있었다. i가 666부터 1씩 증가하는 while문이 있다. 만약 i를 str로 바꾼 문자열 내부에 '666'이 있다면 cnt를 1 증가시켜준다. cnt가 입력값인 n과 일치한다..

[문제] https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net [풀이] 분해합은 n과 n을 이루는 각 자릿수의 합을 구해야 하는데 N을 이루는 각 자릿수의 합을 구하는 부분을 브루스 포스 알고리즘으로 풀어야겠다고 생각했다. 1부터 n+1까지 반복문을 돈다. str함수를 통해 i를 자리수마다 쪼개 리스트 A에 넣는다. 숫자 전체인 i와 자리수의 합인 sum(A)를 더해 res 변수에 넣는다. 만약 res가 n과 같다면 i값..

[문제] https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net [풀이] 간단한 문제인데 삼중 for문의 범위 지정이 가장 신경 써야 할 부분 같다. 특정 카드를 한 장 뽑았다면 다시 그 카드를 뽑을 수 없기 때문에 세 반복문의 index가 겹치지 않아야 한다. 세 카드를 더했을 때 m을 넘지 않는 값 중 가장 큰 값을 구해준다. [코드] import sys if __name__ == '__main__': n, m = ..

[문제] https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net [풀이] 1. 보드가 8*8보다 큰 경우 어느 행, 열을 시작점으로 두고 체스판을 만드는지에 따라 다시 칠해야 하는 정사각형의 개수가 달라진다. 따라서 반복문을 통해 a를 행의 시작점으로 잡았을 때와 b를 열의 시작점으로 잡았을 때의 모든 경우를 다 돌아본다. for a in range(n-7): for b in range(m-7): 2. 행과 열의 시작점을 기준으로 8칸씩 체크한..

[문제] https://www.acmicpc.net/problem/1969 1969번: DNA DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오 www.acmicpc.net [풀이] DNA 리스트를 열 단위로 봤을 때 가장 많을 것을 한 개씩 고른다. 예를 들어 첫 번째 열에서 문자 A가 가장 많을 경우 결과로 출력될 첫 번째 문자는 A가 된다. Hamming Distance의 합은 DNA의 수 n에서 가장 많이 나온 문자의 개수 max(A)를 빼면 가장 많이 나온 문자와 일치하지 않는 갯수가 나온다. [코드] i..