구빙그르르르

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 한줄 이해 -N개의 도시가 주어지고 M개의 버스들이 출발 도시에서 도착 도시까지 가는 비용을 가지고 있을때 원하는 시작 도시에서 도착 도시까지의 최소 비용 구하기 생각난 풀이 1번째 방법: 오랜만에 다익스트라 문제를 만났다. 다익스트라가 무엇이냐 하면 간단히 얘기하면 특정 노드에서 다른 노드로 갈 수 있는 최소 가중치를 가지도록 하는것이다. 이때 다익스트라를..

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 한줄 이해 -N*N 의 그래프가 주어질때 (x1,y1) - (x2,y2)까지의 합 구하기 생각난 풀이 1번째 방법: 문제 이름이 대놓고 누적합이라 어떤식으로 디피에 저장을 해서 이용을 할까 생각을 했다. 이때 dp에 그래프를 순차적으로 돌면서 합을 저장 해놓고 이를 활용 하면 된다고 생각 했다. 이유는 그림에서 설명한거 처럼 구하고자 하는 범위까지 ..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제 한줄 이해 -2행 n열의 스티커가 있고 스티커의 점수가 있을때 주어진 조건에 맞춰서 높은 점수를 확보하도록 스티커를 떼기 생각난 풀이 1번째 방법: DP가 떠올라서 점화식을 어떻게 세울까 고민했다. 먼저 스티커를 골라갈때 2가지 경우가 있다. 지그재그로 갈건지 바로 다음칸은 뜯지 않고 다다음칸에 더 큰 점수를 갖는 스티커를 뜯을지이다. 그렇다면 DP에 어떤값을 저장하고 어떻게 활용..

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 한줄 이해 -A숫자를 B번 곱한뒤 C로 나눈 나머지 구하기 생각난 풀이 1번째 방법: A를 1~B번 곱해가면서 각각 C로 나눈 나머지가 규칙을 이룰 것이라 생각하고 다음과 같이 코드를 짰다. import sys a,b,c = map(int,sys.stdin.readline().split()) dp = [] cnt = 0 for i in range(b): cnt +=1 now = a**i % c if now in dp: cnt -= 1 break dp.app..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 한줄 이해 -N개의 집이 있을때 문제에 주어진 규칙에 따라 집에 색칠을 칠할때 최소비용 구하기! 생각난 풀이 1번째 방법: 처음에는 첫번째 집이 각각 R, G, B의 경우에 따라 모든 경우의 수를 재귀함수를 통해 구현했다. import sys n = int(sys.stdin.readline()) homes = [] for i in range(n): homes.append..

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 문제 한줄 이해 -A숫자를 2배, A숫자 뒤에 1 붙이기를 해가면서 B가 되기위한 최소 횟수 구하기 생각난 풀이 1번째 방법: 숫자의 연산을 해주고 탐색을 진행하는 BFS 아이디어를 떠올려 적용해봤다. 이유는 A 2*A A1 이런식으로 계속 숫자들이 뻗어 나가기 때문이다. import sys from collections import deque #숫자에 1을 붙여주기위해 문자연산이 가능하게 str로 a, b = map(str,sys.stdin.readline().split()) que = deque() #큐에 횟수와 현재..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 한줄 이해 -노드들의 부모트리 찾기 생각난 풀이 1번째 방법: 노드들의 연결 정보를 인접행렬로 나타내 bfs 탐색을 통해 확인 하려 했다. 이때 큐에 연결된노드와 현재 노드를 같이 넘겨주고 꺼낼때마다 visited에 방문을 표시할겸 부모노드의 번호로 바꿔줬다. import sys from collections import deque n = int(sys.stdin.readline()) visited = [0] * (n+1) graph = [[0 for i..

https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 한줄 이해 -주어진 N개의 숫자 중에서 M개를 뽑을때 이미 선택된 숫자를 뽑아되는 경우에서 겹치지 않는 수열 구하기 생각난 풀이 1번째 방법: 이전 N과 M의 문제와 아이디어는 같지만 추가된 조건이 있다. 1부터 N까지 숫자가 아닌 주어진 N개의 숫자 중에서 M개를 뽑아야 하는점, 비내림차순으로 출력해야하는 점 백트래킹이 생각나 재귀를 통한 DFS를 사용했다. 일단 기본적인 아이디어..

https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 한줄 이해 -1부터 N까지의 숫자 중에서 M개를 뽑아 겹치지 않는 수열 출력 생각난 풀이 1번째 방법: 백트래킹이 생각나 재귀를 통한 DFS를 사용했다. 이때 재귀함수를 실행할때 인자를 현재 i값을 통해 넘어줬다. -> why? 문제에서 우선 같은 수를 여러번 골라도 된다고 한다. 그렇다는건 현재 선택된 수가 다시 담겨도 된다는 뜻이기 때문이다. 예를 들어 4 2 예제일때 함수실행 순서는 ..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제 한줄 이해 -5가지 테트리스에서 사용되는 모양들을 그래프에 위치 시켰을때 놓여진 부분들의 합이 제일 큰경우를 구하기 생각난 풀이 1번째 방법: 먼저 도형들의 규칙성을 찾으려고 노력했다. 각 점의 기준에서 상하좌우로 움직이면서 DFS로 탐색을 진행하면 원하는 모양을 만들 수 있는 것이다! 근데 ㅜ 이 모양은 DFS로 탐색을 진행한다고 해서 만들어 질 수 없는 모양이라 따로 처리를 해줘야한다고 ..