알고리즘/백준 문제풀이

문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 풀이 dp, 세번 연속으로 1칸씩 이동하는 경우는 없어야 하므로, dp[i]가 두번째 1칸씩(stairs[i-1] + stairs[i-2]) 이동이라면 dp[i-3]을 더해줘서 무조건 불연속하게 만들기 코드 import sys input = sys.stdin.readline N = int(input().strip()) stairs = [int(input().strip()) for _ in range..

문제 https://www.acmicpc.net/problem/15664 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 풀이 백트래킹 코드 import sys input = sys.stdin.readline N, M = map(int,input().split()) LIST = sorted(list(map(int,input().split()))) total = [] visited = [0 for _ in range(N)] def back(s): if len(total) == M: print(*total..

문제 https://www.acmicpc.net/problem/22953 문제 풀이 이분탐색, 백트래킹, 코드의 주석 참조 코드 import sys input = sys.stdin.readline N, K, C = map(int,input().split()) A_list = list(map(int,input().split())) #격려를 요리 중에 하는게 아니고 최초에 1회만 함 def food_cnt(t_list, t): #t초에 만들 수 있는 요리의 갯수 total = 0 for i in range(len(t_list)): total += t//t_list[i] return total def total_time(t_list, K): #K개의 요리를 하는데 A_list[i]가 몇번씩 반복되는가 #완전탐..

문제 https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 문제 풀이 bfs나 dfs로 풀이 bfs, dfs 둘 다 S부터 시작하면 시간초과,, T부터 시작해야 연산횟수를 줄일 수 있다. S부터 시작하면 시간초과임. 방문한 지점을 또 방문하는 경우는 없으니 visited는 처리하지 않아도 된다. 코드 1) dfs import sys input = sys.stdin.readline S = input().stri..

문제 https://www.acmicpc.net/problem/12101 12101번: 1, 2, 3 더하기 2 n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다. www.acmicpc.net 문제 풀이 dp로 푸는 경우) https://cccaaa.tistory.com/84 처럼 dp를 구성하고, 3이하의 표현방법이 나올때까지 돌리기.. 그림으로 나타내면 이므로, n dp[n]: print(-1) exit() while True: if n

문제 https://www.acmicpc.net/problem/11123 11123번: 양 한마리... 양 두마리... 얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지. 그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!" www.acmicpc.net 문제 풀이 섬의 갯수를 찾는 bfs 코드 import sys input = sys.stdin.readline import collections def bfs(MAP): visited = [[0 for _ in range(len(MAP[0]))] for _ in range(len(MAP))] move = {(-1,0),(0,-1),(1,0),(0,1)} total = 0 f..

문제 https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 문제 풀이 구현문제.. rotatition과 melt에서 최적화가 중요한 부분,, 코드 import sys input = sys.stdin.readline import collections ''' 13:00 시작 파이어스톰 1) 격자를 2^L x 2^L 크기의 부분 격자로 나누기 2) 모든 부분 격자를 시계방향으로 90도 회전 3) 얼음이 있는 칸 3개 or 그 이상과 인..

문제 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 풀이 위 그림처럼 4를 표현할때, 1+ 시작하는 값에서 1+를 떼고 보면 3을 표현하는 모든 방법의 수이다. 2+는 4-2 = 2를 표현하는 방법의 수이고, 3+는 4-3 = 1을 표현하는 방법의 수이다. 정리하면, 4는 3을 표현하는 방법의 수 + 2를 표현하는 방법의수 + 1을 표현하는 방법의 수 이다. (중복되는 값은 없음. 왜냐면 1+2+1 와 2+1+1 는 다른 방법으로 세야하니까) 이런식으로 i번째는 1+(i-1)번째의 표현 방법의 수 + 2+(i-2)수의 표현 방법 + 3..