본문 바로가기

Algorithm475

[파이썬] 백준 2253 : 점프 (골드4) [파이썬] 백준 2253 : 점프 (골드4) https://www.acmicpc.net/problem/2253 문제 N(2 ≤ N ≤ 10,000)개의 돌들이 같은 간격으로 놓여 있다. 편의상 순서대로 1, 2, …, N번 돌이라고 부르자. 당신은 현재 1번 돌 위에 있는데, 이 돌들 사이에서 점프를 하면서 N번째 돌로 이동을 하려 한다. 이때 다음 조건들이 만족되어야 한다. 이동은 앞으로만 할 수 있다. 즉, 돌 번호가 증가하는 순서대로만 할 수 있다. 제일 처음에 점프를 할 때에는 한 칸밖에 점프하지 못한다. 즉, 1번 돌에서 2번 돌이 있는 곳으로 점프할 수 있다. 그 다음부터는 가속/감속 점프를 할 수 있는데, 이전에 x칸 점프를 했다면, 다음번에는 속도를 줄여 x-1칸 점프하거나, x칸 점프하거.. 2024. 2. 18.
[파이썬] 백준 2253 : 점프 (골드4) [파이썬] 백준 2253 : 점프 (골드4) 2253번: 점프 N(2 ≤ N ≤ 10,000)개의 돌들이 같은 간격으로 놓여 있다. 편의상 순서대로 1, 2, …, N번 돌이라고 부르자. 당신은 현재 1번 돌 위에 있는데, 이 돌들 사이에서 점프를 하면서 N번째 돌로 이동을 하려 www.acmicpc.net 문제 풀이 0. 방향성 생각 전형적인 2차원 DP 같은 노드 x라도 어떤 속도로 접근했냐에 따라서 다음의 선택지가 바뀌므로 위치 x와 속도 v로 DP 테이블을 만든다 x번째 발판에 속도 v로 도달했을 때 최솟값을 DP에 기록하자. N = 10000이므로 최대 속도는 약 141이다. cf) 1+2+...+k = {k*(k-1)}/2 > N인 k를 찾는다. sqrt(20000) 넉넉잡아서 최대 속도를 1.. 2024. 2. 7.
[파이썬] 백준 14466 : 소가 길을 건너간 이유 6 (골드 4) [파이썬] 백준 14466 : 소가 길을 건너간 이유 6 (골드 4) 14466번: 소가 길을 건너간 이유 6 첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. www.acmicpc.net 문제 풀이 0. 방향성 생각 각 소에서 BFS를 돌려서 도달하지 못하는 소의 수를 카운트한다. 다리가 있는 간선을 이용해야하면 이동하지 않는다. 쌍을 구하는 문제이므로 A->B, B->A 이런식으로 중복으로 카운팅이 된다. 이를 제거하기 위해서 소의 수를 모두 구한 후 2로 나누어주기. 1. 입력 from collections import deque i.. 2024. 1. 29.
[파이썬] 프로그래머스 : n+1 카드게임 (Lv.3) [파이썬] 프로그래머스 : n+1 카드게임 (Lv.3) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 방향성 생각 각 원소가 겹치지 않음 -> 두 자연수로 n+1를 만드는 경우는 유일함 (a가 정해지면 나머지는 n+1-a) 두 장을 뽑아서 기존의 패와 매칭할 수 있으면 코인을 사용해서 패에 넣기 매칭할 수 없으면 temp에 넣어놓기. hand 내에서 2장 내기 안되는 경우 hand 와 temp를 매칭해서 2장 내기. temp 내에서 코인 하나를 사용하기 안되는 경우 temp 내에서 매칭해서 2장 내기. temp 내에서 코인 두개를 사용하기 그렇지 않.. 2024. 1. 18.

티스토리툴바