1이 될 때까지 1) 문제 해결 아이디어 N에 대해 최대한 많이 나누기(2번 연산)을 수행 N의 값을 줄 일 때, 2 이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 훨씬 많이 줄일 수 있음 2) 정당성 분석 Q. 가능하면 최대한 많이 나누는 작업이 최적의 해를 항상 보장할 수 있는가? K가 2 이상이면 K로 나누는 것이 1을 빼는 것보다 항상 N을 빠르게 줄일 수 있음 3) 소스코드 n, k = map(int, input().split()) count = 0 # 최소 횟수 while True: # 탈출 조건 if(n == 1): break # n이 k로 나누어 떨어지면 나누기 if(n % k == 0): n /= k # n이 k로 나누어 떨어지지 않으면 빼기 else: n -= 1 count += ..
거스름 돈 1) 해결 아이디어 최적의 해: 가장 큰 화폐 단위부터 돈을 거슬러 주기 (500->100->50->10) 2) 정당성 분석 Q. 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유는? 동전의 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 최적의 해가 나올 수 없기 때문 if) 화폐 단위 500, 400, 100원으로 800원을 거슬러 줘야 한다면? 그리디 해: 500 * 1 + 100 * 3 => 4개 최적의 해: 400 * 2 => 2개 3) 소스코드 n = 1260 count = 0 # 동전 개수 # 큰 단위부터 확인 coinList = [500, 100, 50, 10] for coin in coinList: count += n // coin #..
6097 - 설탕과자 뽑기 h, w = map(int, input().split()) # 세로, 가로 n = int(input()) # 막대 개수 board = [[0] * w for _ in range(h)] # h * w 2차원 리스트 # 막대 놓기 for i in range(n): l, d, x, y = map(int, input().split()) # 막대 길이, 방향(0: 가로, 1: 세로), 좌표(x, y) if(d == 0): # 가로 막대 for j in range(l): board[x-1][y-1+j] = 1 elif(d == 1): # 세로 막대 for j in range(l): board[x-1+j][y-1] = 1 # 보드 출력 for i in range(h): for j in ra..
6096 - 바둑알 십자 뒤집기 board = [] for i in range(19): board.append(list(map(int, input().split()))) # 리스트 삽입 n = int(input())# 좌표 개수 for i in range(n): x, y = map(int, input().split())# 십자 뒤집기할 좌표 # 반전(뒤집기) for i in range(19): for j in range(19): if(board[x - 1][j] == 0): board[x - 1][j] = 1 elif(board[x - 1][j] == 1): board[x - 1][j] = 0 if(board[i][y - 1] == 0): board[i][y - 1] = 1 elif(board[i][y ..
6095 - 바둑판에 흰 돌 놓기 n = int(input()) board = [[0] * 19 for _ in range(19)] # 19 * 19 2차원 리스트 for i in range(n): x, y = map(int, input().split()) board[x-1][y-1] = 1# 바둑돌 위치 체크 for i in range(19): for j in range(19): print(board[i][j], end=" ") print() 리스트 컴프리헨션 대괄호 안에 조건문, 반복문을 적용해 초기화하는 방식 [ [0] * m for _ in range(n) ]
6094 - 이상한 출석 번호 부르기3 (풀이1) min() 함수로 최소값 찾기 n = int(input()) num = map(int, input().split()) #최소값 구하기 print(min(num)) min() 데이터들 중 최솟값 반환 max() 데이터들 중 최댓값 반환 (풀이2) for문을 이용한 정석적인 방식 n = int(input()) randomNum = list(map(int, input().split())) # 랜덤 출석 번호 min = 1e9 #최대값으로 설정 for i in range(n): if(randomNum[i] < min): min = randomNum[i] print(min)
6093 - 이상한 출석 번호 부르기2 (풀이1) for문 range()를 이용한 방식 n = int(input()) num = input().split() #리스트 for i in range(n-1, -1, -1): print(num[i], end=" ") ''' for i in range(n): print(num[n-1-i], end=" ") ''' range(n-1, -1, -1) 인 이유는? 역순 출력을 위해 마지막 인덱스 (n-1)을 시작점으로 하고 증감을 -1 로 한다. (n-1) ~ 0 인덱스에 대해 반복을 위해서 끝을 0이 아닌 -1로 해야한다. range(시작, 끝, 증감): 시작 ~ 끝 이전 인덱스 까지 증감 반복 (풀이2) reverse() / reversed()함수를 이용한 리스트 ..
6092 - 이상한 출석 번호 부르기1 countNum = [0] * 23 # 불린 번호를 카운팅할 리스트 n = int(input()) randomNum = list(map(int, input().split()))# 불린 번호 리스트 # 불린 번호 카운팅 for i in range(n): countNum[randomNum[i] - 1] += 1 for i in range(23): print(countNum[i], end = " ") map 함수 반환 값은 map 객체이므로 리스트나 튜플로 이용할 경우, 형변환이 필요하다!
