아이테킨의 끄적끄적

한시간 가량 고민하다가 결국 구글에 검색하고야 말았다...ㅠㅠ 이 문제를 푸는 아이디어는 누적합까지는 모든 무게의 경우를 만들 수 있다는 것이다. 예를 들어 1,2,3의 추가 있다고 한다면 누적합 6(1+2+3) 까지의 무게를 무조건 만들 수 있다는 것이다. 그리고 이 누적합+1 의 값보다 큰 추가 다음으로 나온다면 (예를들어 8이 나온다면) 누적합 +1(7) 이 주어진 추들로 측정할 수 없는 양의 정수 무게중 최소값이다. 누적합까지의 모든 경우의 수가 만들어 질 수 있다는 아이디어, 이건 평소 숫자에 대해서 얼마나 친한지?, 센스인것 같다. 내 머리가 조금 딱딱한 듯 하다... 더 유연하게 생각할 수 있기를! 이런 방법도 있음을 기억해두자. # 2437번: 저울 n = int(input()) scale..

그리디문제로 나는 행렬이 들어가기만 하면 어렵다 ㅠㅠ # 1080번: 행렬 # 다시풀기 n,m = map(int,input().split()) graph1 = [] graph2 = [] cnt = 0 def convertgraph(i,j): for x in range(i,i+3): for y in range(j,j+3): graph1[x][y] = 1- graph1[x][y] for i in range(n): graph1.append(list(map(int,input()))) for i in range(n): graph2.append(list(map(int,input()))) for i in range(n-2): for j in range(m-2): if graph1[i][j] != graph2[i][j..

그리디 문제로 발생할 수 있는 경우의 수를 차근차근 따져보면서 풀어보면 된다. 우선 이 문제는 사야하는 줄보다 더 많이 사도 된다는 것이 포인트이다. 그래서 6개 세트로 넉넉하게 살 경우 1개를 낱개로 맞춰서 사는 경우보다 저렴할 경우 넉넉하게 사도 된다. 또 놓치지 말아야 할 부분은 6개 세트가 낱개로 6개를 살때보다 항상 싸다는 말은 없다. 따라서 이 부분도 신경을 써주어야 한다. 이를 코드로 표현하면 아래와 같다. # 1049번 기타줄 n,m = map(int,input().split()) line_set = [] line_ = [] for i in range(m): a,b = map(int,input().split()) line_set.append(a) line_.append(b) e = min(..

쉬운 문제인듯 하다 정답률도 높다.(70퍼 이상) 최소값을 만들땐 6을 5로 바꿔주고 최대값을 만들땐 5를 6으로 바꿔주면 된다. # 2864번: 5와 6의 차이 a,b = map(int,input().split()) min_a = '' for i in str(a): if i == '6': min_a += '5' else: min_a += i min_b = '' for i in str(b): if i == '6': min_b += '5' else: min_b += i max_a = '' for i in str(a): if i == '5': max_a += '6' else: max_a += i max_b = '' for i in str(b): if i == '5': max_b += '6' else: max..

A에서 B를 만드는것이 아니라 반대로 B에서 A를 만드는 방향으로 생각해서 풀었다. B를 10으로 나눈 값이 1 이거나 B가 2로 나누어떨어질때마다 카운트를 계속 해주고 B가 A보다 작거나 위의 조건을 만족시키지 못하는 수(한자리 홀수)가 나오면 카운트를 -1로 정의해주면 된다. 처음 풀 때 한자리 홀수를 생각하지 않고 단순히 b B a,b = map(int,input().split()) cnt = 1 while True: if b == a: break elif (b%2 != 0 and b % 10 != 1) or (b

그리디 문제인만큼 어떤 딱 떠오르는 아이디어를 찾으려고 하기보다는 생각나는대로 생각을 이어가보았다..!! 우선 양수와 음수를 따로 리스트로 변수설정을 해줬다. 양수 리스트에서는 큰 수 끼리 곱해서 더해줄 떄 가장 큰 값을 가지므로 내림차순, 음수 리스트는 작은수 끼리 곱해서 더해줄 때 (음수 * 음수 = 양수)가 되므로 오름차순으로 정렬했다. 그리고 큐 자료구조를 이용해서 양수,음수 리스트에서 하나하나 빼가면서 나중에 한꺼번에 곱해줄 리스트(ans)에 추가해줬다(append) 이후 조건에 대한 자세한 설정은 문제에 나와있는 예제들을 하나하나 만족시켜가면서 만들어 본 것이다. 운좋게 한번에 통과가 되었다. 역시 그리디 문제는 겁먹지 말고 조금 지저분한데 싶더라도 일단 해보는게 가장 좋은 전략인듯 싶다! #..

중간의 뒤집는 숫자의 개수가 얼마나 많던지 상관없이 숫자가 얼마나 바뀌는지만 잘 계산하면 풀리는 문제다. 0 -> 0번 바뀜 -> 0번 뒤집음 01 -> 1번 바뀜 -> 1번 뒤집음 010 -> 2번 바뀜 -> 1번 뒤집음 0101 -> 3번 바뀜 -> 2번 뒤집음 01010 -> 4번 바뀜 -> 2번 뒤집음 010101 -> 5번 바뀜 -> 3번 뒤집음 0101010 -> 6번 바뀜 -> 3번 뒤집음 이렇게 계산되므로 규칙을 생각해보면 바뀌는 수(count) 에 1을 더한 수를 2로 나눈 나머지가 뒤집는 횟수가 된다. num = input() count = 0 for i in range(len(num)-1): if num[i] != num[i+1]: count += 1 print((count+1)//2)

이 문제를 풀때의 아이디어는 나머지의 크기에 따라서 답이 달라진다는 것이다. 나머지가 연속으로 사용할 수 있는 기간(L)과 비교해서 큰 경우와 작은경우 케이스별로 처리하면 된다. 사실, 그냥 생각나는대로 풀어보았는데 운좋게 한번에 맞았다. 어떻게 이렇게 풀게 되었는지 설명하기가 애매한 듯 싶다. 이게 그리디 문제의 특징이 아닌가 싶다...? 라는 개인적인 생각.. 크흠... # 4796 캠핑 case = 0 while True: case += 1 L, P, V = map(int, input().split()) if (L + P + V) == 0: break remainder = V%P if V%P

우선순위 큐의 힙 자료구조를 이용하면 문제를 풀 수 있다. 처음에 이 문제를 풀 때 '힙(heap)'이라는 자료구조를 생각해내지 못해서 한참을 헤맸다. 이 문제를 풀때 가장 중요한 아이디어는 힙(heap)이라는 생각이다. 알고리즘은 이러하다. 0) 총 비교한 횟수(answer)를 0으로 둔다. 1) 현재의카드 묶음(card_deck) 중 가장 작은 2개의 카드 묶음을 꺼낸다. 2) 두 개를 더한 값 = 현재 단계에서 비교한 횟수 3) 두 개를 더한 값을 총 비교한 횟수(answer)에 더해준다. 4) 두 개를 더한 값을 다시 카드 더미(card_deck) 안에 넣는다. 5) 1 ~ 4 과정을 힙에 하나의 덱만 남을 때 까지 반복한다. (참고. https://claude-u.tistory.com/341) ..

30의 배수 중 가장 큰 수를 찾아서 출력해내는 문제이다. 위키피디아에 배수 판정법이라는 것을 알게되었다. https://ko.wikipedia.org/wiki/%EB%B0%B0%EC%88%98_%ED%8C%90%EC%A0%95%EB%B2%95 배수 판정법 - 위키백과, 우리 모두의 백과사전 배수 판정법은 배수인지 확인하려는 수의 배수가 맞는지 간단히 확인하는 것이다. 배수인지 확인하려는 수가 클 때에는 나눗셈을 이용하여 계산하는데 시간도 오래 걸리고 틀린 답이 나올 수 ko.wikipedia.org 결국 문제는 30의 배수인지 확인하는 것이기 때문에 위키피디아에서 나온 개념을 적용하면 될 것 같다. 3의 배수는 각 자리 숫자의 합이 3의 배수인 수이다. 30의 배수는 3의 배수이면서 일의 자리가 0인 ..