(C++) - 백준(BOJ) 12101번 : 1, 2, 3 더하기 2
www.acmicpc.net/problem/12101 12101번: 1, 2, 3 더하기 2 n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다. www.acmicpc.net backtracking문제였습니다. 풀이방법 1. 1,2,3중에 중복가능하게 i개를 골라 식을 만들었을 때 num과 같다면 vector 변수 ans에 넣어줍니다. 2. 매번 3개의 분기로 호출이 되므로 시간복잡도는 i * 3^i 가 됩니다. Code #include using namespace std; int n,k; vector ans; void backtracking(int idx,int m,int num,string op){ if(idx ..
(C++) - 백준(BOJ) 20056번 : 마법사 상어와 파이어볼
www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 구현문제였습니다. 풀이방법 1. 파이어볼은 행,열,질량,속도,방향 5개의 정보를 포함하고 있습니다. 구조체를 이용해줍니다. 해당 구조체들을 원소로 파이어볼들의 정보를 담은 vector 변수 fireBalls, 격자의 정보를 저장할 vector변수 board를 선언해줍니다. 그리고 8방향을 표현할 dx,dy배열, 모두 홀수또는 짝수 방향일 때 분산시킬 방향의 정보를 담는 o..