본문 바로가기

Algorithm475

[파이썬] 프로그래머스 : 연속 펄스 부분 수열의 합 (레벨3) [파이썬] 프로그래머스 : 연속 펄스 부분 수열의 합 (레벨3)https://school.programmers.co.kr/learn/courses/30/lessons/161988풀이방향성 생각입력보고 $O(N)$으로 비벼야겠다고 생각state는 1이 곱해졌는지, -1으로 곱해졌는지 2가지로 나뉘길래 2차원 dp만들고 $O(N)$으로 순회dp배열에는 현재 1 혹은 -1이 곱해졌을 때 부분 수열의 합의 최대값을 기록한다dp배열에는 최대값을 끝까지 가지고 있지 않다 (다음 위치에는 부분 수열의 합이 작아질수도) -> max(dp[0]), max(dp[1]) 비교 전체코드def solution(arr): N = len(arr) dp = [[0]*N for _ in range(2)] dp[0][0.. 2025. 3. 23.
[파이썬] 프로그래머스 : 미로 탈출 명령어 (레벨3) [파이썬] 프로그래머스 : 미로 탈출 명령어 (레벨3)https://school.programmers.co.kr/learn/courses/30/lessons/150365풀이방향성 생각정해는 그리디 + 조건많은 분기?처음 위치 유형을 나누고, 최소 거리로 이동하고 남는 거리가 발생했을 때 이 거리를 d l로 우선순위를 줘서 푸는 문제인듯?근데 50 * 50 * 2500 = 625만이라 BFS도 될거같아서 비벼봤다.시간대별 맵의 배열을 3차원으로 만들기 전체코드from collections import dequedef solution(n, m, x, y, r, c, k): H,W,sy,sx,ey,ex = n,m,x-1,y-1,r-1,c-1 x_dist, y_dist = ex-sx, ey-sy .. 2025. 3. 23.
[파이썬] 프로그래머스 : 주사위 고르기 (레벨3) [파이썬] 프로그래머스 : 주사위 고르기 (레벨3)https://school.programmers.co.kr/learn/courses/30/lessons/258709  풀이방향성 생각10C5 : 주사위를 반으로 나누는 모든 경우의 수6^10 : 승률 계산하는 경우의 수 (6^5씩 양 플레이어 둘)주사위 수는 1~100까지고, 중복된 수를 줄이기 위해 6^5 리스트 대신 딕셔너리로 관리한다. 전체코드from collections import Counterdef solution(dice): n = len(dice) r = n//2 def dfs(score, cnt): if cnt == r: scores.append(score) return .. 2025. 3. 23.
[파이썬] 백준 2003 : 수들의 합 (실버4) [파이썬] 백준 2003 : 수들의 합 (실버4)https://www.acmicpc.net/problem/2003풀이방향성 생각누적합입력이 10000이라 N^2도 될 줄 알았는데, 숫자가 커서 그런가 TLE해시 써서 O(N)으로 풀이 파이썬from collections import defaultdict as ddN,target = map(int,input().split())arr = list(map(int,input().split()))cs = 0table = dd(int)table[0] = 1answer = 0for a in arr: cs += a if cs - target in table: answer += table[cs-target] table[cs] += 1print.. 2025. 3. 22.

티스토리툴바