25.03.18 코딩테스트 대비

2025. 3. 19. 00:20·알고리즘/코딩테스트 대비

BOJ 2096. 내려가기


 

2096번: 내려가기

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.먼저 처음에 적혀 있는 세 개의 숫자 중에서

www.acmicpc.net

 

 

 

내 코드

import sys

input = sys.stdin.readline

n = int(input())

dp1 = [0, 0, 0]
dp2 = [0, 0, 0]

for _ in range(n):
    nums = (list(map(int, input().split())))
    dp1[0], dp1[1], dp1[2] = min(dp1[0], dp1[1]) + nums[0], min(dp1) + nums[1], min(dp1[1], dp1[2]) + nums[2]
    dp2[0], dp2[1], dp2[2] = max(dp2[0], dp2[1]) + nums[0], max(dp2) + nums[1], max(dp2[1], dp2[2]) + nums[2]

print(max(dp2), min(dp1))

처음 문제를 봤을 때 bfs나 dfs로 풀어야할까 했는데 이렇게 풀면 무조건 시간초과가 걸릴 것 같아 dp로 접근하여 문제를 해결했다.

 

최솟값과 최댓값을 구해야하기 때문에 dp1, dp2를 만들었고, nums 값들을 입력받을 때마다 dp1은 다음과 같은 점화식으로 업데이트 해 나갔다.

 

dp1[0] = min(dp1[0], dp1[1]) + nums[0]

dp1[1] = min(dp1) + nums[1]

dp1[2] = min(dp1[1], dp1[2]) + nums[2]

 

dp2는 위 점화식에서 min을 max로 바꿔주면 된다

 

dp2[0] = max(dp2[0], dp2[1]) + nums[0]

dp2[1] = max(dp2) + nums[1]

dp2[2] = max(dp2[1], dp2[2]) + nums[2]

 

마지막에는 print(max(dp2), min(dp1))을 통해 정답을 출력할 수 있다.

 

처음에 풀었을 때는 계속 메모리초과가 나서 뭐가 문제일까 생각하다가 nums에 모든 줄에 [a, b, c]를 저장해놓아서 그런 것 같았다. 

 

굳이 저장을 안해놓고 해도 문제를 해결할 수 있을 것같아 위와 같이 코드를 수정하고 정답을 맞을 수 있었다.

 

 

내 제출

 

 

 

BOJ 13549. 숨바꼭질 3


 

13549번: 숨바꼭질 3

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면

www.acmicpc.net

 

 

내 코드

from collections import deque
import sys

input = sys.stdin.readline

n, k = map(int, input().split())
q = deque([(0, n)])
visited = [False] * 100001
visited[n] = True

while q:
    time, x = q.popleft()
    if x == k:
        print(time)
        break

    for nx in [x*2, x-1, x+1]:
        if 0 <= nx < 100001 and not visited[nx]:
            visited[nx] = True
            if nx == x*2:
                q.append((time, nx))
            else:
                q.append((time+1, nx))

bfs로 해결할 수 있었다.

 

현재 위치와 시간을 deque에 저장하면서 진행했다.

 

처음에는 (0, n)을 q에 저장했고, 이를 기점으로 다음 위치와 그 위치에 도달한 시간을 저장했다.

 

이 때, 2*x는 0초가 걸리기 때문에 deque에 (time, nx)로 저장했고, 그 외에 나머지는 1초가 걸리기 때문에 (time+1, nx)로 저장했다.

 

이러다가 deque에서 popleft한 x가 k와 같다면 time을 출력하고 정답을 맞출 수 있었다.

 

 

내 제출

 

 

BOJ 1043. 거짓말


 

1043번: 거짓말

지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서

www.acmicpc.net



내 코드

import sys

input = sys.stdin.readline

n, m = map(int, input().split())

know = set(list(map(int, input().split()))[1:])

parties = []
for _ in range(m):
    parties.append(list(map(int, input().split()))[1:])

while True:
    updated = False

    for party in parties:
        if all(person not in know for person in party):
            continue
        for person in party:
            if person not in know:
                know.add(person)
                updated = True

    if not updated:
        break                

answer = 0
for party in parties:
    if all(person not in know for person in party):
        answer += 1

print(answer)

그냥 쉽게 접근해서 풀었다.

 

먼저 지민이의 대해 아는 사람들을 know라는 set에 저장해두었다.

 

그리고 각 파티들의 참가자들을 parties에 저장해 두었다.

 

각 party에 know에 있는 사람이 있으면 그 party에 있는 사람들을 모두 know에 저장했다.

 

위 과정을 know에 사람들이 추가가되지 않을 때까지 반복했다.

(처음에는 이 위 과정을 업데이트가 끝날때까지 반복하지 않고 한번만 했다가 문제를 틀렸다...)

 

그리고 각 party에 대해서 그 party에 오는 사람들 모두가 know에 저장되어 있지 않으면 answer를 +1해주었다.

 

마지막에는 이 answer를 출력하여 정답을 맞을 수 있었다.

 

 

내 제출

'알고리즘 > 코딩테스트 대비' 카테고리의 다른 글

25.03.21 코딩테스트 대비  (0) 2025.03.22
25.03.20 코딩테스트 대비  (0) 2025.03.21
25.03.19 코딩테스트 대비  (0) 2025.03.19
'알고리즘/코딩테스트 대비' 카테고리의 다른 글
  • 25.03.21 코딩테스트 대비
  • 25.03.20 코딩테스트 대비
  • 25.03.19 코딩테스트 대비
Laewon Jeong
Laewon Jeong
  • Laewon Jeong
    래원
    Laewon Jeong
    글쓰기 | 관리
  • GitHub

    • github.com/laewonJeong
  • 전체
    오늘
    어제
    • 분류 전체보기 (172)
      • Docker 및 Kubernetes (11)
        • Docker (5)
        • Kubernetes (6)
      • Data Engineering (18)
        • Hadoop (5)
        • Spark (5)
        • Kafka (5)
        • Airflow (3)
      • CI|CD (3)
      • 알고리즘 (136)
        • 알고리즘 (2)
        • LeetCode (118)
        • 프로그래머스 (11)
        • BOJ (1)
        • 코딩테스트 대비 (4)
      • 서버 (2)
        • 미니 서버 (2)
      • 잡담 (1)
  • 태그

    도커
    dfs
    코딩테스트
    분산
    분산처리
    BFS
    leetcode
    백트래킹
    프로그래머스
    리트코드
    Apache Spark
    아파치 하둡
    그래프
    이진탐색
    programmers
    누적합
    아파치 스파크
    String
    우선순위큐
    알고리즘
    파이썬
    티스토리챌린지
    DP
    문자열
    Kubernetes
    Python
    오블완
    쿠버네티스
    docker
    heapq
  • 인기 글

  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
Laewon Jeong
25.03.18 코딩테스트 대비
상단으로

티스토리툴바