![]()
https://www.acmicpc.net/problem/16198 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 처음 문제를 봤을 때 그리디로 접근해도 될 것 같았다. 각 단계에서 얻을 수 있는 최대 값을 구해서 구슬이 2개만 남았을 때 그 값들을 모두 합하려고 했다. N = int(input()) li = list(map(int, input().split())) ans = 0 while len(li)!=2: power = [] for i in range(1,len(li)-1): power.append..
문제링크 https://www.acmicpc.net/problem/1548 1548번: 부분 삼각 수열 세 수 x, y, z가 x+y>z, x+z>y, y+z>x의 관계를 만족하면, 세 수는 삼각관계에 있다고 한다. 마찬가지로 길이가 N인 수열 B(b[0], b[1], ..., b[n-1])의 모든 b[i], b[j], b[k]가 삼각관계에 있으면 이 수열은 삼각 www.acmicpc.net 코드 n = int(input()) data = sorted(list(map(int,input().split()))) if n>2: result = 2 for start in range(n-2): end = start+2 while True: if data[start] + data[start+1] > data[end..
https://www.acmicpc.net/problem/17265 17265번: 나의 인생에는 수학과 함께 세현이의 인생의 목표는 1분 1초 모든 순간 수학과 함께 살아가는 것이다. 그렇기 때문에 매일 수학을 생각하면서 살아가고 있다. 세현이는 밥을 먹을 때도 쌀알의 수를 계산하여 칼로리를 바로 www.acmicpc.net 문제 분석 난이도 골드5 분류 그래프 탐색, 브루트포스 들어가기 전에 파이썬으로 풀면 eval로 굉장히 쉽게 풀 수 있다고 생각했지만 그런 문제는 아니였다. 문제 세현이의 인생의 목표는 1분 1초 모든 순간 수학과 함께 살아가는 것이다. 그렇기 때문에 매일 수학을 생각하면서 살아가고 있다. 세현이는 밥을 먹을 때도 쌀알의 수를 계산하여 칼로리를 바로 계산하고 한걸음 한걸음 보폭을 계..
![]()
1895번: 필터 (acmicpc.net) 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 소스코드 문제풀이 이미지 크기는 R x C이므로 R,C 값을 입력 받음 이미지의 한 줄을 하나의 리스트로 R개를 img라는 리스트에 입력받아 이중 리스트 생성 T 값을 입력 받고 공백 리스트인 arr와 ans 생성 이미지를 3x3 크기로 필터링 할 때 중앙값을 찾는 fun(i,j) 함수 필터 크기가 3x3이므로 한 줄의 연속 3개의 수를 arr에 추가를 3번 반복 9개의 정..
![]()
풀이 이동하고자 하는 채널은 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/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) 이..
![]()
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,..
정답코드 # 복습 횟수:0, 00:30:00, 복습필요X from copy import deepcopy answer = 10 def dfs(begin, target, words, cnt, visited: list): global answer # 탈출 조건 if begin == target: answer = min(answer, cnt) return for i in range(len(words)): if visited[i] == 1: continue check = [] for j in range(len(words[i])): if begin[j] != words[i][j]: check.append(j) if len(check) == 1: visited[i] = 1 # 방문처리 tmp = deepcopy(be..
