![]()
풀이 이동하고자 하는 채널은 500,000번 까지 이지만 윗 채널에서 밑 채널로 이동할 수도 있기 때문에 1,000,000 번 채널까지 탐색을 해주어야 한다. 목표 채널로의 이동은 번호를 눌러서 이동한 채널 -> + or - 키를 사용하여 원하는 채널로의 이동이기 때문에 (번호를 눌러 이동한 채널의 자리수) + (목표 채널과 이동한 채널의 차이) 가 눌러야 하는 버튼의 수이고 이를 완전탐색을 하여 눌러야 하는 횟수를 구한다. 코드 import sys def main(): N = int(sys.stdin.readline()) M = map(int, sys.stdin.readline()) A = list(map(int, sys.stdin.readline().split())) count = abs(100 - ..
https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 알고리즘 완전탐색 문제다. 문제에서 "요리의 쓴맛과 신맛은 모두 1,000,000,000보다 작은 양의 정수라고 했기 때문에 브루트포스임을 단번에 파악할 수 있었다. 신맛과 단맛을 저장해서 선택하여 곱과 합을 조합해줘야 하기 때문에 combination 함수를 사용했다. 브루트포스 알고리즘은 조건을 빼먹지 않고 구현하는 것이 핵심이기 때문에, 하나하나 구체적으로 코드를 작성하..
https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 입력 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지..
![]()
1895번: 필터 숫자 9개가 오름차순이나 내림차순으로 정렬되어 있을 때, 중앙값은 다섯 번째 숫자이다. 예를 들어, 1, 3, 4, 1, 2, 6, 8, 4, 10의 중앙값은 4이다. (1 ≤ 1 ≤ 2 ≤ 3 ≤ 4 ≤ 4 ≤ 6 ≤ 8 ≤ 10) 이미지 I는 www.acmicpc.net 문제코드
![]()
-문제 -풀이 주어진 DNA배열들의 각 자리별 DNA물질의 빈도를 체크한다. 각 자리별 가장 많은 빈도의 물질을 구하고, 이를 자리별로 연결하면 DNA s를 얻어 낼 수 있다. 이때 DNA s를 구성하는데 사용되지 않은 물질은 Hamming distance를 발생한다. 그래서 각 자리별 성분의 빈도수를 확인할때 가장 큰 빈도는 s의 물질로 취하고, 나머지 물질들의 빈도수의 합은 결과적으로 Hamming distance의 총합이 된다. -코드 #include #include #include #include using namespace std; int main(){ int N, M; cin >> N >> M; string arry[N]; for(int i = 0 ; i > ar..
![]()
풀이 순열을 사용한 완전탐색 기법 이용 순환 첫번째 값을 1~n까지 진행하여 모든 순열을 표시해주면 되는데 algorithm헤더의 next_permutation을 이용하여 편리하게 모든 순열을 구할 수 있었다. vector에 1~n까지 차례로 값을 넣어주고 next_permutation을 이용해 순열을 구하는 코드이다. 코드 #include #include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector p(n); for (int i = 1; i
https://www.acmicpc.net/problem/9663 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. main ideas 1. 어차피 matrix로 두어도 같은 행과 열에는 퀸을 못 두므로 이차원배열이 아니라 일차원 배열로 풀 수 있다. 2. 퀸이 있는 곳과 같은 행, 같은 열, 대각선에는 다른 퀸을 놓지 못한다. 따라서 일차원 배열의 i 번째 열에 퀸을 놓고, 열이 겹치거나 대각선에 있다면 중지한다. (backtracking) 이..
![]()
https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 문제분석 소스코드 input = __import__('sys').stdin.readline N = int(input()) bigBag = N // 5 while bigBag >= 0: if (N - bigBag * 5) % 3 == 0: print(bigBag + ((N - bigBag * 5) // 3)) break if bigBag == 0 and N % 3 != 0: print(-1) break big..
![]()
1. 문제 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net 2. 해결방법 - 완전 탐색을 이용했다 ! N,M은 50보다 작거나 같은 자연수이다. 그럼 N*M정사각형 좌표 하나씩을 다 탐색해봤자 25000~ 완전 탐색을 하기엔 충분한 숫자라고 판단했다. - 우선 사각형을 2중 리스트로 입력받는다. - k(사각형 길이 탐색) 변수를 두고 i,j(사각형 좌표)에서 (i, j) , (i,j+k) , (i+k, j), (i+k, j+k)가 같은 k를 탐색한다. - 가장 큰 k로 계속 side 갱신 !! 3. 코드 n,..
![]()
[Problem] [Solution] 예시) 크기가 2인 도미노 세트에 찍혀 있는 점의 개수를 구해보자. 윗칸에 찍히는 점의 개수가 0인 경우: 아랫칸에 찍히는 점의 개수 0개, 1개, 2개 윗칸에 찍히는 점의 개수가 1인 경우: 아랫칸에 찍히는 점의 개수 1개, 2개 윗칸에 찍히는 점의 개수가 2인 경우: 아랫칸에 찍히는 점의 개수 2개 따라서 (0+0) + (0+1) + (0+2) + (1+1) + (1+2) + (2+2) = 12로 총 12개가 답이다. 문제로 다시 돌아가 크기가 N인 도미노 세트에 찍혀 있는 점의 개수를 구해보자. 1. 정수형 변수 n을 초기화한다. 2. n값을 입력 받는다. 3. 점의 개수를 저장할 정수형 변수 sum을 0으로 초기화 한다. 4. for문을 활용하여 0부터 n까지..
![]()
문제 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net Algorithm 1번 규칙에 의해 N=1일때 이친수는 1개[1]이고,2번 규칙에 의해 N=2일때 이친수는 1개[10]가 된다. N=3일때는 N=2일때 이친수의 끝자리가 0이므로 [100,101]이 나올수 있으므로 2개이다. N=4일때는 N=3일때 이친수의 끝자리가 0일때는 [1000,1001]이 나오고, 1일때는 [1010]이 나오게 된다. N이 점점 커져서 k일때를 가정해보자...
![]()
https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제분석 소스코드 import sys N, M = map(int,input().split()) chess = [] result = [] for i in range(N): chess.append(list(sys.stdin.readline().strip())) for i in range(0,N-7): for j in range(0,M-7): count1 = 0 count2 = 0 for k i..
