생각 생각

https://acmicpc.net/problem/1256 1256번: 사전 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되 www.acmicpc.net 간만에 자력으로 풀어낸 수학 문제. 풀이과정 처음부터 끝까지 군더더기가 없어서 좋았다. import sys input=sys.stdin.readline N,M,K=map(int,input().strip().split()) answer='' dp=[[1 for _ in range(M+1)] for _ in range(N+1)] for i in range(1,N+1): for j in range(1,M+1): dp[i..

https://acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net n log n 의 LIS. 이제 적응해서 외워서 어렵지 않게 쓸 수 있다. from bisect import bisect_left import sys input=sys.stdin.readline num = int(input()) a = list(map(int, input().split())) b = [a.pop(0)] for i in a: if b[-1] < i: b.append(i)..

https://acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net DFS+DP가 필요한 상황은 이제 어느 정도 볼 수 있게 되었다. 다만 새로 배웠던 것은 사이클 탐지를 위해 백트래킹까지 곁들여 이용할 수 있다는 부분. import sys input=sys.stdin.readline sys.setrecursionlimit(10**6) N,M=map(int,input().split()) graph=[[int(i) if i.isnumeric() else i for i in..

https://acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 브루트포스 문제임은 범위로 바로 알 수 있었다. 식을 어떻게 세울지가 관건이었다. eval()은 알고만 있고 써 본 적은 없는데, 이렇게 쓰게 될 줄은 몰랐다. import sys from itertools import combinations input=sys.stdin.readline N=int(input()) ex=input().strip() l_ex=[i if not i.isnume..

https://acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 최댓값을 구하는 문제이니 어쨌거나 dp일 것이라 생각했다. dfs와 연관지어서 하기가 조금 헷갈렸다. dfs를 할 때 특정 조건이면 return True(아니면 값)을 해서 하나의 경로를 찾는 것에 적응하자. import sys input=sys.stdin.readline sys.setrecursionlimit(10**6) n=int(input()) graph=[list(map(int,inpu..

최대 유량 문제의 관건은 결국 어떤 식으로 유량을 보낼 것이라 판단하는지일 것 같다. 이제 대회 알고리즘이라 꽤 어려운데, 그래도 어느 정도 이해는 된다. 예제로 이 문제를 풀어봤다. https://www.acmicpc.net/problem/2367 2367번: 파티 첫째 줄에는 N, K, D가 주어진다. 다음 줄에는 D개의 정수가 주어지는데, 이는 각 음식의 종류마다 가져올 수 있는 양의 제한을 의미한다. 이 값은 N보다 작거나 같은 음이 아닌 정수이다. 다음 N개 www.acmicpc.net import sys input=sys.stdin.readline N,K,D=map(int,input().split()) Ds=list(map(int,input().split())) vs=[[False]*(N+D+..

https://acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 많이 꼬였다. 미리 거리를 구해두는 게 훨씬 빠르다는 것을 알게 되었다. import sys from collections import deque input=sys.stdin.readline N,M,F=map(int,input().split()) graph=[list(map(int,input().split())) for _ in range(N)] sy,sx=map(..

https://acmicpc.net/problem/1111 1111번: IQ Test 다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다. www.acmicpc.net 사실상 그냥 다 하는 브루트포스이다. 숫자가 하나나 둘이면 바로 끝. 아니라면 하나하나 계산을 해보기 시작한다. 다만 어느 범위에 대해 해보아야 할 지가 고민이었는데, 질문게시판에서 능력자분들이 200이래서 그런갑다 했다.. import sys input=sys.stdin.readline N=int(input()) lis=list(map(int,input().split())) answer=False if N==1: print("A") exit(0) elif N==2: i..