본문 바로가기

Algorithm475

[파이썬] 백준 2481 : 해밍 경로 (골드2) [파이썬] 백준 2481 : 해밍 경로 (골드2) 2481번: 해밍 경로 길이가 같은 두 개의 이진수 코드 w1과 w2가 있다고 하자. 이 두 코드 사이의 해밍 거리(Hamming distance)는 w1과 w2의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 www.acmicpc.net 문제 풀이 0. 방향성 생각 입력 개수가 최대 10^6, 해밍거리가 1인 노드끼리만 연결해주면 된다. 노드가 최대 10^6인거부터 2개씩 짝지어서 하는 방법은 불가능. 최대 5 * 10^11이므로 불가능하다. 코드인덱스 매칭을 통해서 딕셔너리를 사용한다는 점까지는 생각할 수 있다. 그 이후에는 1. 입력 from collections import deque import sys input .. 2023. 8. 12.
[파이썬] 백준 23290 : 마법사 상어와 복제 (골드1) [파이썬] 백준 23290 : 마법사 상어와 복제 (골드1) 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net 문제 풀이 0. 방향성 생각 같은 격자에 같은 방향을 가진 물고기들이 매우 많아질 수 있다. 테스트 케이스를 보면 답이 60만이 넘어가기도 한다. 예를들어 리스트로 사용하면 특정 좌표에만 [1,1,2,3,4,4,4,4,4,4,5,7,7,.........,8] 이런식으로 매우 길어질 수 있다. 이를 간단하게 처리하기 위해 딕셔너리를 사용. 딕셔너리[좌표][물고기 방향] =.. 2023. 8. 11.
[파이썬] 백준 17244 : 아맞다우산 (골드2) [파이썬] 백준 17244 : 아맞다우산 (골드2) 17244번: 아맞다우산 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출 www.acmicpc.net 문제 풀이 0. 방향성 생각 기본적으로 DP에서 하던거처럼 상태를 나눈다. 물건의 개수가 늘어갈수록 상대가 2배로 늘어나니 bitmask를 통해서 간편하게 처리한다는게 아이디어 1. 입력 from collections import deque import sys input = lambda : sys.stdin.readline().rstrip() w,h = map(int,input().split()) arr .. 2023. 8. 9.
[파이썬] 백준 2342 : Dance Dance Revolution (골드3) [파이썬] 백준 2342 : Dance Dance Revolution (골드3) 문제 풀이 0. 방향성 생각 발 옮기기 전 위치 -> 옮긴 후 위치 비용을 정리하는 딕셔너리 cost 정의 25개 상태 왼발5가지*오른발5가지, 각 상태로 올 수 있는 경우 중 가장 작은 코스트 선택 입력으로 1 2 2 4 0이 들어오면 마지막 0은 제외하고 stage 0에서 4개의 단계를 거쳐 stage 4에 도달해야한다. 각 stage에 도달하는 모든 상태를 확인하면서 DP 업데이트. 1. 입력, DP 초기화 import sys input = lambda : sys.stdin.readline().rstrip() command = list(map(int,input().split())) stages = len(command).. 2023. 8. 8.

티스토리툴바