문제링크 https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 코드 import sys n = int(input()) result = [] def isgood(arr): for i in range(1,len(arr)//2+1): if arr[-i:]==arr[-i*2:-i]:return False return True def dfs(): global result if len(result)==n: print(''.join(map(str,result))) sys.e..
Koala - 11기
풀이 백트래킹 문제이다. 먼저 입력값으로 주어지는 배열의 크기 N과 부분수열의 합 S를 입력는다. 배열 arr[20]에 N개의 원소를 입력받는다. 재귀 함수 dfs를 구현합니다. 이 함수는 현재 인덱스(idx)와 현재까지의 합(sum)을 인자로 받는다. 재귀 함수 dfs의 동작은 다음과 같다: 현재 인덱스의 원소를 합에 더해줍니다: sum += arr[idx]; 만약 합이 S와 같다면, 카운트를 증가시킵니다: if (sum == S) { cnt++; } 현재 인덱스의 다음 원소부터 탐색하기 위해 for문을 사용하여 재귀 호출합니다: for (int i = idx + 1; i < N; i++) { dfs(i, sum); } 모든 원소에 대해 dfs를 호출하여 부분수열의 합이 S와 같은 경우의 수를 구한다...
https://www.acmicpc.net/problem/2057 2057번: 팩토리얼 분해 음 아닌 정수 N이 주어졌을 때, 이 수를 서로 다른 정수 M(M ≥ 1)개의 팩토리얼의 합으로 나타낼 수 있는지 알아내는 프로그램을 작성하시오. 예를 들어 2=0!+1!로 나타낼 수 있지만, 5는 이와 같은 www.acmicpc.net 문제 분석 난이도 실버5 분류 수학, 브루트포스 들어가기 전에 숫자의 크기를 보고 대략적인 감을 잡을 수 있다면 정말 편하다. 문제 문제 풀이 풀이 입력 제한의 최댓값보다 20!이 더 큰 수이다. 즉 0~20 총 21가지에 대해 포함 / 비포함으로 탐색을 하면 된다. 그럴 경우 2^21가지 경우의 수로 200만정도로 충분히 브루트 포스로 풀어볼 수 있다. 소스코드 def bf(n..
문제 https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 문제 설명 장부에 K번만큼 숫자를 쓰거나 지우는데, 입력받는 숫자가 0이면 가장 최근 숫자를 지우고 0이 아니라면 해당 수를 쓴다. 최종적으로 0이 아닌 숫자들의 합을 구하면 된다. 코드 #include #include using namespace std; int main() { int K; cin >> K; int total = 0; stack accoun..
문제 https://www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net 풀이 방법 n과 m이 50보다 작거나 같은 자연수이므로 완전 탐색으로 가능하다 생각하여 삼중 for문을 이용하여 풀이했습니다. n x m에서 나올 수 있는 가장 큰 정사각형부터 감소하는 방향으로 for문을 작성하고, 왼쪽 위의 꼭짓점이 될 수 있는 i, j를 이중 for문으로 모두 탐색합니다. 0,0 ([i][j])부터 변의 길이가 s인 정사각형의 꼭짓점을 비교하여 모두 같다면 정사각형의 크..
문제 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 알고리즘 분류 수학 다이나믹 프로그래밍 그리드 알고리즘 문제 설명 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로..
https://school.programmers.co.kr/learn/courses/30/lessons/67257 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제의 설명이 매우 길어 링크로 대신 첨부합니다. 해결방법: 주어진 입력 값이 적을 때에는 재귀보다 직접 연산을 이용 제한사항 expression은 길이가 3 이상 100 이하인 문자열입니다. expression은 공백문자, 괄호문자 없이 오로지 숫자와 3가지의 연산자(+, *) 만으로 이루어진 올바른 중위표기법(연산의 두 대상 사이에 연산기호를 사용하는 방식)으로 표현된 연산식입니다. 잘못된 연..
문제 코드 코드 설명 1. 두 수를 비교하는 문제이기 때문에 먼저 a, b의 입력을 받아야 한다. -> a, b = map(int, input().split()) 2. a가 b보다 클 경우에는 '>'를 출력하고, a가 b보다 작을 때는 '
문제 13423번: Three Dots (acmicpc.net) 풀이방법 처음엔 vector에 넣어서 정렬 후 풀었는데 시간 초과가 나왔다. 그래서 입력된 점들을 자동으로 오름차순으로 정렬하는 Set에 넣었다. 간격이 같은 세 점을 각각 A, B, C라고 한다면 A와 B를 지정하고 B + B - A인 C가 Set에 있다면 +1. 지금보니까 왜 변수 명을 i, j로 안하고 iter_i, iter_j로 했지?? 코드가 더러워졌다 코드 #include #include using namespace std; int T; // test case int N; // Number of Dots int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(..
https://www.acmicpc.net/problem/1551 1551번: 수열의 변화 첫째 줄에 수열의 크기 N과 K가 주어진다. N은 20보다 작거나 같은 자연수이고, K는 0보다 크거나 같고, N-1보다 작거나 같은 정수이다. 둘째 줄에는 수열이 ‘,’로 구분되어 주어진다. 수열을 이루 www.acmicpc.net 문제 분석 분류 수학, 구현, 문자열, 시뮬레이션, 파싱 문제 설명 크기가 N인 수열 A가 주어졌을 때, 세준이는 인접한 두 원소의 차이를 이용해서 크기가 N-1인 수열 B를 만들 수 있다. 예를 들어, A = {5, 6, 3, 9, -1} 이었을 때, B = {6-5, 3-6, 9-3, -1-9} = {1, -3, 6, -10}이 된다. 즉, B[i] = A[i+1]-A[i]가 된다..
문제 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 알고리즘 분류 수학 다이나믹 프로그래밍 그리디 알고리즘 문제 설명 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로..
Problem Solution int형인 num을 1씩 늘리고 string 형태로 변환하여 "666" 이 있다면 count를 하나씩 늘려 가면서 n번째 영화의 제목에 들어간 수를 출력하도록 코드를 작성한다. Answer #include #include using namespace std; string getNumber(int n) { int count = 0; int num = 0; while (count > n; string ans = getNumber(n); cout
