![]()
https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제 분석 코드 #include #include #include using namespace std; int n, c,x; vector v; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> c; int num; for (int i = 0; i < n; +..
![]()
https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 문제 해석 N * M 크기의 방이 존재한다. 이 방의 가장자리는 모두 벽으로 이루어져 있고, 추가적인 벽이 존재 할 수 있다. 벽은 1, 빈 공간은 0으로 입력된다. 로봇 청소기는 다음과 같은 규칙을 통해 동작한다. 1. 현재 위치를 청소한다. 2. a. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향이 청소하지 않은 공간이라면 회전하고, 전진한 후 1번부터 진행한다. b. 현재 위치에서 현재 방..
https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 문제분석 대표적인 투포인터 알고리즘 문제이다. 리스트를 탐색하면서 탐색한 리스트의 합이 m이면 카운트를 하여서 경우의 수를 출력하면 되는 문제이다. 수열의 개수와 나와야 하는 합을 첫째 줄에 입력받고 다음 줄에 해당 수열을 입력받는다. 코드 n, m = map(int, input().split()) s = list(map(int, input().split(..
https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 문제 분석 N개의 정수로 이루어진 수열 A[1],A[2],...,A[N]이 있다. 이 수열에서 두 수를 골랐을 때( 같은 수도 가능) 그 차이가 M 이상이면서 제일 작은 경우를 구하라 ※근데 같은 수를 골랐는데 차이가 생길 수도 있나..? 아무튼, 예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M = 3일 경우, 1 4, 1 5, 2 5를 골랐을 때 그 차이가 ..
![]()
https://velog.io/@jay6768/BOJ-Python-16395-파스칼의-삼각형 Intro 이항계수를 삼각형 형태로 배열한 파스칼의 삼각형. n번째 행의 k번째 수를 구하는 문제이다. n=3, k=2라면 정답은 2이다. Solution 크기를 n으로 하여 삼각형을 의미하는 배열 arr을 미리 만들어둔다. n번째 행의 k번째 수는 n-1번째 행의 k-1번째 수와 k번째 수를 더한 값이다. Code def main(): n, k = map(int, input().split()) arr = [[1]*i for i in range(1, n+1)] for i in range(2, n): for j in range(1, i): arr[i][j] = arr[i-1][j-1] + arr[i-1][j] pr..
![]()
https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 해석 N 개의 수가 주어지면 주어진 조건을 사용하여 1로 만드는 최소 연산 횟수를 구하는 문제이다. 예시로 10의 경우에 10 > 9 > 3 > 1 로 바꿀 수 있으므로 3을 출력해야 한다. 코드 input = __import__('sys').stdin.readline n = int(input()) dp = [-1] * 1000001 dp[0] = 0 dp[1] = 0 dp[2] = 1 dp[3] = 1 for i in range(4,n+1): dp[i] = dp[i-1] + 1 if i % 2 == 0:..
https://www.acmicpc.net/problem/13699 13699번: 점화식 다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t(0)=2 t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5 ... 주어진 입력 0 ≤ n www.acmicpc.net 문제분석 점화식 t(n)이 주어지고 정수를 입력받아 점화식에 해당하는 정수를 대입했을 때의 값을 출력하는 되는 문제이다. 문제에 t(0), t(1), t(2), t(3)이 주어져 있으므로 이를 이용하여 점화식을 만들면 된다. 코드 n = int(inp..
![]()
https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 분석 코드 #include #include #include using namespace std; int n,m; int dp[1001],arr[1001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; //memset(dp..
![]()
https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 문제 해석 N 개의 수가 주어지고, 주어진 수들의 소수의 개수를 구하는 문제이다. 코드 input = __import__('sys').stdin.readline n = int(input()) ans = 0 arr = list(map(int, input().split())) for i in arr: if i < 2: continue flag = True j = 2 while j * j
https://velog.io/@jay6768/BOJ-Python-1969-DNA [BOJ / Python] 1969 - DNA 백준 1969번 DNA velog.io Intro DNA가 무엇인지, Hamming Distance가 무엇인지 구구절절 설명해놓아 어려운 듯했지만 주어진 입력 문자열들에서 자리마다 가장 자주 등장하는 문자를 모두 더해 새로운 문자를 만들어내는 방식으로 풀 수 있다. Solution n개의 문자열을 입력한다. m회 반복하며 그 내부에서 모든 DNA를 자리마다 순회하며 등장하는 문자의 개수를 센다. key를 문자, value를 개수로 하여 딕셔너리 변수 count에 저장한다. 반복마다 가장 자주 등장한, 즉 count에서 value가 가장 큰 문자 key가 문자열 변수 result..
문제분석 입력받은 10개의 문자열 중에서 찾으려는 문자열이 한번이라도 있는 지를 확인하는 문제이다. 유념해야 하는 부분은 입력받은 10개의 문자열을 처음과 뒤가 이어져 있는 반지라고 가정한다는 점이다. 또한 찾으려는 문자열이 한번이라도 나오면 카운트 한다는 점을 알면 좀 더 쉽게 풀 수 있다. 코드 k = input() n = int(input()) ans = 0 for _ in range(n): s1 = input() s = s1 * 2 for i in range(len(s)): if k==s[i:i+len(k)]: ans += 1 break print(ans) 문제풀이 찾으려는 문자열, 반지의 개수를 입력받고 반지에 적힌 문자열을 입력받는다. 중요한 점은 반지의 처음과 끝이 이어져 있기 때문에 입력받..
https://www.acmicpc.net/problem/15664 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제분석 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하라! 조건 1. N개의 자연수 중에서 M개를 고른 수열 조건 2. 비내림차순 -> 길이가 K인 수열 A가 A1≤A2≤...≤Ak−1≤Ak 를 만족해야 한다. - 입력으로는 첫째 줄에 N과 M이 주어진다. (1≤M,N≤8) 둘째 줄에는 N개의 수가 주어지는데, 이는 10,000보다 작..
