파이썬

11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 풀이 과정 그래프 문제에서 노드간에 걸리는 시간이 음수가 포함했다? -> 벨만 포드 음수 간선에 관하여 최단 경로 문제는 다음과 같이 분류할 수 있다. 1. 모든 간선이 양수인 경우 2. 음수 간선이 있는 경우 2-1) 음수 간선 순환은 없는 경우 2-2) 음수 간선 순환이 있는 경우 벨만 포드 최단 경로 알고리즘은 음의 간선이 포함된 상황에서도 사용할 수 있다. 또한 음수 간선의 감지할 수 있으며, 벨..

5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 풀이 과정 1. n이 100개라고 브루트 포스로 풀면 안 된다.. 100개의 데이터가 나올 경우, 나올 수 있는 가지 수가 2^99가 나온다. 이 문제는 dp문제로 문제에서 주어진 0보다 크거나 같고 20보다 작거나 같은 조건을 이용해서 해결해야 한다. 2. dp의 크기를 21으로 할당해준다. 그리고 주어진 배열(arr)의 첫 번째 인덱스의 값을 dp의 인덱스에 1로 설정한다. 첫 번째 숫자는 반드시 포함되어야 하기 때문에!! 3. 이중 반복문을 사용하였..

17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 풀이 과정 1. bfs로 해결을 하였다. q에는 x, y 좌표 값과 이동 시간, 무기를 갖고 있는지 확인용 key 값을 1x4 배열로 넣어줬다. 2. 주의할 점은 방문 표시를 n x m 행렬로 해주면 안 된다. n x m으로 방문 표시를 하면 용사가 무기를 가질 때, 용사가 무기가 없어서 우회했던 경로를 다시 방문할 수 없기 때문에 시간 초과가 발생할 것이다. 3. q에서 pop을 할 때 x, y 값이 공주가 있는 곳(n-1, m-1)으로 올 경우..

Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 풀이 과정 1. 규칙성을 찾는다. 4 - > 9 - > 25 -> 81 4 -> ((2 * √4) -1)^2 -> ((2 * √9) -1)^2 -> .... 풀이 코드 start = 4 for _ in range(int(input())) : start = int(((start ** (0.5)) * 2 - 1 ) ** 2) print(start)

23843번: 콘센트 광재는 전자기기 대여사업을 시작했다. 퇴근하기 전에 다음날 손님들에게 빌려줄 N개의 전자기기를 충전하려 한다. 사용 가능한 콘센트는 M개가 있고, 성능은 모두 동일하다. 전자기기들은 한 www.acmicpc.net 풀이 과정 1. 입력받은 충전 시간 배열을 내림차순 정렬을 시킨다. 2. 콘센트 배열을 생성시킨다. 3. 내림차순 정렬된 충전 시간을 콘센트 배열에 삽입한다. 3-1 ) 만약 콘센트 배열의 크기가 주어진 콘센트 개수(m) 보다 작을 경우 -> 콘센트 배열에 해당 time을 삽입 3-2 ) 만약 콘센트 배열의 크기가 주어진 콘센트 개수(m) 이상일 경우 -> 가장 작은 값 + 현재 time을 더해서 다시 삽입 4. 콘센트 배열에 있는 값 중 가장 큰 값을 출력한다. -> 가..

18430번: 무기 공학 첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내 www.acmicpc.net 풀이 과정 (처음 시도) 처음에는 이중 for문으로 방문하지 않은 i, j가 있다면 해당 위치가 중앙으로 두었을 때 문제에서 요구하는 이미지가 형성되고, 방문하지 않은 이미지라면 방문 체크하고 탐색하게끔 설정하였는데, 이렇게 두면 아무리 가로 세로 크기가 5 이하여도 시간 초과가 발생한다. ㅠㅠ 1. 다른 분의 코드를 참고해서 이중 for문을 사용하지 않고 오른쪽 열로 하나씩 좌표 값을 탐색 인자에 넣어줬다. 그리고 행이 n과 같을 경우 강도의 ..

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번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. 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..