Language/Python 썸네일형 리스트형 [파이썬][백준 16198][백트래킹] 에너지 모으기 - 컴도리돌이 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 풀이 과정 1. 주어진 n의 개수가 너무나 작기 때문에 모든 경우의 수를 구해주면 된다. 2. i번째를 삭제할 경우의 현재 에너지양 + w[i-1] * w[i+1], i번째를 제외한 w 배열, depth - 1로 탐색을 한다. 3. depth 가 3일 될 경우 경우의 수가 배열의 맨앞의 에너지 값 * 배열의 마지막 에너지 값만 계산 할 수 있기 때문에 해당 값과 현재 에너지를 더해서 반환해준다. 4. 가장 큰 값을 반환해준다. 풀이 코드 import sys;.. 더보기 [파이썬][백준 14501][그리디] 퇴사 - 컴도리돌이 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 과정 1. 걸리는 일수(t)와 현재 일수(i)의 합이 n을 넘어가면 안되기 때문에 t+i가 n을 넘어가면 현재 일수보다 앞에 있는 일수의 값을 갖고 온다. 2. n을 넘어가지 않으면 현재 일수(i)보다 앞에 있는 일수(i+1)와 i+t 일수에 p를 더한 값과 비교해서 큰 값을 할당해 준다. 풀이 코드 import sys; input = sys.stdin.readline n = int(input()) arr = [list(map(int,input().split())) for _ in range(n)] dp = [0] * (n+ 1) for i in range(n-1,-1,-1) : t,p = ar.. 더보기 [파이썬][백준 1082][DP][그리디] 방 번호 - 컴도리돌이 1082번: 방 번호 스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이고, M원을 모두 사용해 www.acmicpc.net 풀이 방법 처음에는 아무 생각 없이 dfs로 5분만에 풀었다. 하지만 다음 테스트 케이스에서 바로 다이나믹 프로그래밍을 전환.. 10 1 1 1 1 1 1 1 1 1 1 50 1. n의 값만큼 가격 p를 입력 받고, dp의 크기를 입력 받은 m+1 만큼 할당해준다(음의 값으로). 2.가격 p를 담고 있는 room의 배열의 마지막 인덱스부터 시작하였다. 마지막 인덱스(방번호)에 해당하는 가격이 x라고 정의할 때, 반복문으로 x 부터 m+1 만큼 dp[현재 요금] = m.. 더보기 [파이썬][백준 2493][스택] 탑 - 컴도리돌이 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 풀이 과정 아마도 스택 문제에서 괄호 문제 다음으로 많이 나오는 스택 문제 유형인 거 같다. 해당 유형을 처음 접하시는 분들은 일단은 머릿속에 배열의 순서를 생각하면서 카피하시면 왜 스택으로 사용하는지 이해가 갈 것이다. (아님 말고~) 1. 스택처럼 사용할 q라는 배열 안에 입력받은 값의 마지막 값과 인덱스를 각각 넣어준다. 그리고 출력할 answer도 따로 입력받은 n의 크기만큼 할당해준다. 2. n-2 번째 인덱스부터 첫 번째 인덱스까지 검사를 시작한다... 더보기 [파이썬][백준 2504][문자열] 괄호의 값 - 컴도리돌이 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 풀이 방법 1. 알고리즘 분류는 스택으로 되어있었지만 해당 문제를 문자열로 해결하고 싶어서 스택을 이용하지 않았다. 2. '(' 과 ')'의 각각의 개수가 다를 경우 또는 '[' 과 ']'의 각각의 개수가 다를 경우 0을 반환해주었다. (올바른 괄호 x) 3. '()' 는 2, '[]'는 3이기에 해당 값들을 replace를 통해서 '+2','+3'으로 바꿔주었다. 4. 3번을 처리해주고 나머지 '(' ,')'은 각각 '+(', ')*2'로 처리해주었다. 5... 더보기 [파이썬][백준 13460][BFS] 구슬 탈출 2 - 컴도리돌이 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 풀이 방법 1. 일단 알고리즘은 BFS를 사용하였다. 2. 큐에는 빨간색 공의 좌표(rx, ry)와 파란색의 공의 좌표(bx, by) 그리고 이동 횟수를 포함하고 있다. 3. 이동 횟수가 10이 넘어가면 break 시키고 -1 값을 반환해주었다. 4. 방문 표시는 빨간색의 공과 파란색의 공을 str으로 변환해주어서 dict에 True로 삽입하여 방문 표시를 체크하였다. 5. 상하좌우 4개의 방향으로 move 함수를.. 더보기 (파이썬) 백준 1015번 : 수열 정렬 - 컴도리돌이 문제 P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다. 배열 A가 주어졌을 때, 수열 P를 적용한 결과가 비내림차순이 되는 수열을 찾는 프로그램을 작성하시오. 비내림차순이란, 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 말한다. 만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다. 입력 첫째 줄에 배열 A의 크기 N이 주어진다. 둘째 줄에는 배열 A의 원소가 0번부터 차례대로 주어진다. N은 50보다 작거나 같은 자연수이고, 배열의 원소는 1,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 비내.. 더보기 (파이썬) 백준 1010번 : 다리 놓기 - 컴도리돌이 https://www.acmicpc.net/problem/1010 문제 재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M) 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다... 더보기 이전 1 2 3 4 5 6 7 8 다음
