https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 현재 위치한 도시에서의 리터당 가격이 다음 도시의 리터당 가격보다 비싸면 사야하는 최소한의 양(다음 도시까지 가는 데 필요한 양) 만큼만 구입하고, 현재 위치한 도시에서의 리터당 가격이 다음 가야하는 곳 보다 싼 경우에는 현재 가격보다 더 싼 도시가 나타날때까지의 거리를 가는 데 필요한 리터만큼 구입한다. import sys input = sys.stdin.readline N = i..
알고리즘💻
https://www.acmicpc.net/problem/11568 11568번: 민균이의 계략 민균이는 요즘 준민이를 놀리는 일에 재미가 들렸다. 오늘도 그는 준민이를 놀리기 위해 한가지 재미있는 아이디어를 떠올렸다. 그는 하나의 정수가 쓰여 있는 카드 N장을 준비하여 준민이에게 www.acmicpc.net 가장 긴 증가하는 부분 수열 문제인데, 문제가 처음 접하는 유형이라 어려웠다. 검색해보니 dp로 푸는 방법과 이진탐색을 이용하는 방법 두 가지가 있던데, 일단 dp로 풀어보았다. dp[i] = num[i]를 마지막 원소로 가질 때 가장 긴 증가하는 부분 수열의 길이, 1로 초기화 dp[i] = 0~i-1까지 중 num[i]보다 작은 인덱스의 dp값 + 1과 dp[i]중 max값 갱신 import s..
https://www.acmicpc.net/problem/1451 1451번: 직사각형으로 나누기 첫째 줄에 직사각형의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 직사각형에 들어가는 수가 가장 윗 줄부터 한 줄에 하나씩 M개의 수가 주어진다. N과 M은 100보다 작거나 같은 자연수이 www.acmicpc.net 1. (0,0)을 왼쪽 위 꼭짓점으로 하고 (i,j)를 오른쪽 아래 꼭짓점으로 하는 직사각형의 누적합을 dp[i][j]에 저장 dp[i][j] = dp[i-1][j] + dp[i][j-1] + arr[i][j] - dp[i-1][j-1] 2. (0,0)을 포함한 작은 사각형이 (0~N-2, 0~M-2) 인 경우 3. (0,0)을 포함한 작은 사각형이 dp[i][M-1]인 경우 4. ..
https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 이것도 꽤 자주? 접했던 유형의 문제였다. n을 1, 2, 3의 합으로 나타내야 할 때 가능한 경우는 n-1 + 1 , n-2 + 2, n-3 + 3의 세 가지 경우이므로 dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 로 구할 수 있다. 초기값 dp[1] = 1 //1 dp[2] = 2 // 2, 1+1 dp[3] = 4 //3, 2+1, 1+2, 1+1+1 import sys input = sys.stdin.readline T = int(input()) dp = [0] * 1..
https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 이것도 dp를 활용하여 푸는 기본적인 유형이었다. 간단하게 점화식을 짤 수 있었다. import sys input = sys.stdin.readline N, M = map(int, input().split()) arr = [] for _ in range(N): arr.append(list(map(int, input().split()))) dp = [[0]*M for _ in rang..
https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net dp를 통해 푸는 방법을 생각하는 것은 어렵지 않았다. n=0, n=1인 경우는 초기값으로 두고 dp[i][j] = arr[i][j] + max(dp[i-1][j-1], dp[i-1][j]) 로 점화식을 생각했는데, 이렇게 하면 j = 0일 때 인덱스에러가 나기 때문에 dp를 [n][n+1] 로 설정하였다. 그 다음에는 n = 0, n = 1일때 예외처리를 하지않아서 인덱스에러가 나왔다..ㅎㅎ import sys input = sys.stdin.readline n = ..
https://www.acmicpc.net/problem/15811 15811번: 복면산?! 복면산이란 수학 퍼즐의 일종으로, 어떤 계산식의 각 숫자들을 특정 문자로 바꾸면 각 문자가 어떤 숫자인지 맞추는 퍼즐이다. 대표적으로 SEND+MORE=MONEY가 있다. SEND + MORE ------ MONEY S=9, E=5, N=6, D=7, www.acmicpc.net DFS 재귀를 이용해서 구현을 했는데 시간초과가 났다. 아예 처음부터 순열을 구해서 부르트포스로 풀면 되는 문제였다. 처음에 접근할 때는 넣을 때부터 덧셈의 결과를 맞춰보려고 생각하다가 막혔는데.. 너무 어렵게 생각했던 것 같다. 각 문자마다 다른 숫자여야 하므로 전체 문자의 개수를 구해 0~9까지 그 개수에 맞게 순열을 뽑으면 된다. ..
https://www.acmicpc.net/problem/2026 2026번: 소풍 만약 K명의 친구 관계인 학생들이 존재하지 않는다면 -1을 출력한다. 그 외의 경우에는, K개의 줄에 학생들의 번호를 증가하는 순서로 한 줄에 한 개씩 출력한다. 여러 경우가 존재한다면 첫 번째 www.acmicpc.net 백트래킹 문제가 항상 어렵다... 재귀 싫어.... 일단 재귀를 사용할 때는 먼저 탈출조건을 적은 후에 차근차근 생각하면 될 것 같다. 1. 먼저 조건을 체크하고, 조건에 맞으면 ans에 추가한다. 2. ans의 길이가 K가 되면 끝낸다. 3. dfs에서 탈출했을 때 pop해야한다. import sys input = sys.stdin.readline K, N, F = map(int, input().sp..
https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 1. 문자열 입력에서 앞 뒤의 '[', ']' 와 숫자 중간의 ','를 제거한다. 2. 큐를 만들어 문자열을 넣는다. 3. flag를 만들어 R이 나오는 경우에는 -1을 곱해준다. 3. D가 나오고 flag가 1인 경우에는 앞에서 pop, flag가 -1인 경우에는 뒤에서 pop 해준다. 4. 마지막으로 flag가 -1이면 배열을 뒤집어준 후 조건에 맞춰 출력한다. import sys from collections import deque input = ..
import sys input = sys.stdin.readline arr = [] for _ in range(9): arr.append(list(map(int, input().rstrip()))) row = [[0]*10 for _ in range(10)] col = [[0]*10 for _ in range(10)] box = [[0]*10 for _ in range(10)] for i in range(9): for j in range(9): n = arr[i][j] row[i][n] = 1 col[j][n] = 1 box[i//3+j//3*3][n] = 1 def solve(cnt): if (cnt==81): for i in range(9): for j in range(9): print(arr[i][..
