접근법 문제를 단순화하고 풀고 싶었는데, 이 문제가 브루트포스 단계에 들어간 데에는 이유가 있었다... 모든 경우의 수를 고려해주면 되는데, 체스판의 형태는 흰색과 검은색으로 시작되는 경우 두 가지다. 따라서 흰색과 검은색 체스판을 필터라고 생각하고 입력값으로 주어지는 체스판을 한칸 한 칸씩 움직여보면서 해당 필터와 비교해서 틀린 칸의 갯수를 세어본다. 여기서 서로 일치하지 않는 칸의 수는 다시 칠해야 하는 칸의 수라고 볼 수 있다. 정리하면, 첫 번째 : 흰색과 검은색으로 시작하는 체스판을 우선 만들어 둔다. ( 이하 필터로 명명함 ) 두 번째 : 입력값으로 주어지는 체스판과 두가지 필터를 한 칸 한 칸씩 모든 경우에 대해서 비교해본다. 세 번째 : 비교해보면서 서로 틀린 칸의 수를 Count한다. 네..
접근법 고민을 많이 해봤는데 생각보다 간단한 문제였다. 간단하게 생각해보면 어쨌든 문제에서 얘기하는 무거움이라는 개념은 키와 몸무게 둘 다 큰 사람이다. 또한, 등수를 매길 때 공동 등수가 들어가기 때문에 그냥 자기보다 크고 무거운 사람이 몇 명인지 Count해서 자기 등수만 정해주면 되는 것이다. 🙃 즉.. n명을 n-1번씩 전수 비교해보면 되는 것이다! 풀이 N = int(input()) st_arr = list() for _ in range(N): weight, height = map(int,input().split(' ')) st_arr.append((weight,height)) for i in st_arr: rank = 1 for j in st_arr: if i[0] < j[0] and i[1]..
접근법 생소한 개념이라 문제를 이해하기 어려웠다. 핵심은 가장 작은 생성자를 구해야 한다는 점이다. 입력값 N이 주어졌을 때 생성자를 만드는 규칙에 따라서 가장 작은 숫자부터 차례대로 확인을 하면 편할 것이다. 즉, 생성자를 만드는 규칙은 모든 자리의 수와 해당 숫자를 더했을 때 입력값 N을 만족시키면 되기 때문에 N의 각 자릿수의 최대값은 9로 N ± ( 자릿수 * 9 ) 만큼의 범위만 확인해주면 된다 ! 예를 들어서 256이라는 숫자라고 한다면 각 자리의 숫자는 가장 큰 숫자가 9이므로 256 - 27 = 229 이므로 229부터 차례대로 규칙에 따라 N을 만족하는지 확인하면 된다. 풀이 def constructor(N): minimum = N - len(str(N)) * 9 minimum = 1 i..
접근법 브루트 포스의 문제는 조금은 무식하게 보일지 모르지만 모든 경우의 수를 보는 것이 맞다. 물론 지금 이 문제는 python의 itertools를 이용해서 조합을 통해 쉽게 풀 수도 있지만 알고리즘의 측면에서 풀어보자. 우선 필자는 아래 코드로 문제를 풀었다. N, M = map(int,input().split(' ')) card = list(map(int,input().split(' '))) res = set() for i in range(N-1): pick = card[i:i+2] # 카드 두 장을 먼저 뽑습니다 other = [x for x in card if x not in pick] # 뽑은 두 장의 카드를 제외한 카드를 리스트에 담습니다. for j in other: if M >= sum..
접근법 재귀의 대표적인 문제 하노이 탑이다. 우선 아래 원판이 4개인 경우를 역순으로 진행해보자. 먼저 4개의 원판을 전부 3위치에 옮겨 놓기 위해서는 아래처럼 2번 위치에 1번, 2번, 3번 원판이 위치해 있어야한다. 그래야 4번 원판을 3번 위치의 가장 아래에 놓을 수 있기 때문이다. 자 그럼 2번 위치에 1, 2, 3 원판이 위치하기 위해서는 1, 2번 원판은 3번에 있어야 한다. 그래야 3번 원판을 2번 위치에 놓을 수 있기 때문이다. 또한 마찬가지로 1, 2번 원판이 3번 위치에 있기 위해서는 1번 원판을 우선 2번 위치에 두어야 한다. 그래야 2번 원판을 3번 위치에 놓을 수 있기 때문이다. 쉽게 일반화 해보자. 가장 먼저 해야할 일은 원판의 갯수 n개가 주어졌을 때, Step 1 : n-1개..
접근법 사실 어떤 규칙이 있는지 찾는데도 시간이 오래 걸렸다. 우선 규칙은 예시로 나와있는 출력을 아래와 같이 줄을 그어보면 찾을 수 있다. 크게 3 * 3 형태의 사각형만 주목해서 보다 보면 정가운데만 공백으로 이루어져 있는 것을 볼 수 있다. 즉, 재귀로 풀 수 있는 냄새가 풀풀난다. 그래서 필자는 문제를 아래와 같이 접근해 보았다. n은 3의 제곱꼴인 수로만 등장하므로 이 규칙을 따라갈 필요가 있다. 규칙에 따라서 주어진 길이에서 3으로 나눈 몫이 1일 경우에는 아예 중앙이 뚫리는 형태, 그 외 몫이 다른 값일 경우에는 최초로 3 * 3의 [ '***', '* *', '***' ] 형태의 사각형이 그대로 채워지는 형태로 코드를 짜보았다. 풀이 def stars(n): matrix=[] for i i..