분류 전체보기

    [백준]9184번 신나는 함수 실행 - DP
    SW개발/코딩테스트

    [백준]9184번 신나는 함수 실행 - DP

    dp = [[[0] * 21 for i in range(21)] for i in range(21)] # 값 저장을 위한 3차원 리스트 def w(a, b, c): if a 20: return w(20, 20, 20) if dp[a][b][c] != 0: # 값이 기억하고 있는 것 -> 바로 출력 return dp[a][b][c] if a < b and b < c: dp[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c) # 점화식 return dp[a][b][c] else: # otherwise dp[a][b][c] = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b..

    [백준]1003번 피보나치 함수 - DP
    SW개발/코딩테스트

    [백준]1003번 피보나치 함수 - DP

    n = int(input()) for i in range(n): case = int(input()) zero = [1, 0, 1] one = [0, 1, 1] if case >= 3 : for i in range(3, case+1): zero.append(zero[i-2]+zero[i-1]) one.append(one[i-2]+one[i-1]) print(zero[case], one[case]) 코드 설명 기본적으로 피보나치 수의 3번째 까지는 0과 1이 등장한 횟수로 초기화하여 준다. 3이상의 숫자가 나올 경우 피보나치의 점화식을 이용하여 zero, one 리스트에 값을 추가하여 준다. Point : DP 이론을 통하여 빠른 시간내에 구할 수 있는 문제이다. 값을 기억하면서 다음 계산에 이용하는 방식이..

    [백준]13305번 주유소 - 그리디
    SW개발/코딩테스트

    [백준]13305번 주유소 - 그리디

    import sys n = int(input()) length = list(map(int, sys.stdin.readline().split())) oil = list(map(int, sys.stdin.readline().split())) sum_ = 0 min_ = 0 for i in range(n - 1): if i == 0: sum_ = oil[0] * length[0] min_ = oil[0] else: min_ = min(min_, oil[i]) sum_ = sum_ + min_ * length[i] print(sum_) 코드 설명 길이와 기름 값 가격을 리스트에 저장하여 둔다. 반복문을 n-1 번 수행한다. 만약 맨 처음일 경우 첫 도로의 길이 * 첫 도시의 가격을 통해 기름을 넣어준다. 다음 ..

    [백준]1449번 수리공 항승 - 그리디
    SW개발/코딩테스트

    [백준]1449번 수리공 항승 - 그리디

    n, l = map(int, input().split()) where = list(map(int, input().split())) where.sort() start = 0 cnt = 0 for loc in where: if start < loc: # 덮혀진 곳은 더 이상 탐색 필요 없음. start = loc + l - 1 # 하나의 테잎으로 끝나는 위치로 갱신해줌. cnt += 1 print(cnt) 코드 설명 수리해야 하는 곳의 위치를 순서대로 하기 위해 입력 받은 후 정렬을 해준다. 이미 끝난 위치를 기록하기 위한 start 변수를 선언하여 준다. 반복문을 돌면서 탐색 시작 위치 보다 수리하려는 위치가 클 경우에만 테잎을 붙히고, 시작 위치를 loc + 테잎의 길이 - 1 로 계속 갱신한다. Poi..

    [백준]4796번 캠핑 - 그리디
    SW개발/코딩테스트

    [백준]4796번 캠핑 - 그리디

    cnt = 1 while True: a = list(map(int, input().split())) if a[0] == 0: break result = (a[2] // a[1]) * a[0] if a[0] < a[2] - ((a[2] // a[1]) * a[1]): result += a[0] else: result += a[2] - ((a[2] // a[1]) * a[1]) print("Case ", cnt, ": ", sep="", end="") print(result) cnt += 1 코드 설명 테스트 케이스를 입력 받으면서 숫자가 0이 나온다면 반복을 종료한다. 먼저 result 값을 V // P * L 의 연산을 이용해 계산하여 준다. 그 후에 이용 가능한 남은 일수를 체크하는데 만약 남은 일수가..

    [백준]1339번 단어 수학 - 그리디
    SW개발/코딩테스트

    [백준]1339번 단어 수학 - 그리디

    n = int(input()) word = [] for i in range(n): word.append(input()) digit = {} for each_list in word: cnt = 0 for i in each_list: if i not in digit: digit[i] = 10 ** (len(each_list) - cnt - 1) # 10의 거듭제곱 형태로 자릿수 설정 else: digit[i] += 10 ** (len(each_list) - cnt - 1) # 자릿수 * 등장 횟수 누적 cnt += 1 digit = sorted(list(digit.values()), reverse=True) # 내림차순으로 정렬 sum = 0 for i in range(len(digit)): sum += d..

    [백준]1946번 신입 사원 - 그리디
    SW개발/코딩테스트

    [백준]1946번 신입 사원 - 그리디

    import sys t = int(sys.stdin.readline()) for i in range(t): n = int(sys.stdin.readline()) grade = [[0] * 2 for i in range(n)] cnt = 1 for j in range(n): grade[j][0], grade[j][1] = map(int, sys.stdin.readline().strip().split()) grade.sort(key=lambda x: int(x[0])) minV = grade[0][1] for x in range(n): if minV > grade[x][1]: minV = grade[x][1] cnt += 1 print(cnt) 코드 설명 테스트 케이스의 숫자 만큼 반복문을 진행한다. 반복문..

    [백준]2217번 로프 - 그리디
    SW개발/코딩테스트

    [백준]2217번 로프 - 그리디

    n = int(input()) weight = [] for i in range(n): weight.append(int(input())) weight.sort(reverse=True) max = weight[0] for i in range(1, n): if max < weight[i] * (i+1): max = weight[i] * (i+1) print(max) 코드 설명 각 무게를 weight 리스트에 입력 받은 후 내림차순으로 정렬한다. 현재까지 가장 큰 값은 weight[0] 이다. 반복문을 수행하면서 weight[i] * (i+1) 의 값이 max 보다 크면 갱신하여 준다. Point : 먼저 중량순으로 정렬해주기 위해 sort(reverse=True) 함수를 이용하여 준다. 맨 처음 최대 중량은 ..

    [백준]5585번 거스름돈 - 그리디
    SW개발/코딩테스트

    [백준]5585번 거스름돈 - 그리디

    n = int(input()) n = 1000 - n answer = 0 while True: if n // 500 >= 1: answer = answer + (n // 500) n = n - ((n // 500) * 500) elif n // 100 >= 1: answer = answer + (n // 100) n = n - ((n // 100) * 100) elif n // 50 >= 1: answer = answer + (n // 50) n = n - ((n // 50) * 50) elif n // 10 >= 1: answer = answer + (n // 10) n = n - ((n // 10) * 10) elif n // 5 >= 1: answer = answer + (n // 5) n = n ..

    [백준]11047번 동전0 - 그리디
    SW개발/코딩테스트

    [백준]11047번 동전0 - 그리디

    n, k = map(int,input().split()) a = [] cnt = 0 for i in range(n): a.append(int(input())) for i in range(len(a)-1, -1, -1): if k < a[i] : continue cnt = cnt + int(k / a[i]) k = k % a[i] if k == 0: break print(cnt) 코드 설명 먼저 a 리스트에 이용가능한 동전의 가치를 저장해준다. 가장 큰 가치를 가진 동전을 먼저 사용해야 하므로 반복문을 거꾸로 수행한다. 만약 동전의 가치가 K원보다 크다면 continue를 통해 다음 반복을 수행한다. 그렇지 않다면 카운트에 그 몫을 더해준다. k 는 나머지 연산을 통해 숫자를 갱신해준다. k == 0 이 ..

티스토리툴바