본문 바로가기

알고리즘/백준42

[백준] 9461파도반수열 c++ https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 수열을 보고 규칙을 찾았을 때는 이 식을 찾았다. P(i)=P(i-2)+P(i-3) (단,i>3) 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16.... 그림을 보면 i번째 삼각형의 한변의 길이는 P(i-1)+P(i-5)임을 알 수 있다. 나는 첫번째 점화식으로 풀었다. 그리고 1~100 까지 P(i)를 출력해보니까 오버플로우가 일어나서 배열을 int 에서 long long으로 바꾸어.. 2022. 3. 24.
[백준]9663N-Queen c++ 1학년 때 수업 교재에 있었는데 못풀었던 기억이 있다. 이번엔 잘 풀려서 뿌듯했다. n-queen은 가로,세로,대각선 방향 (2개) 에 하나의 퀸이 들어가야하는 문제이다. 가로,세로,대각선 두방향을 체크해줄 배열을 총 4개 만든다. 예를 들어 4 퀸이고 좌표가 2,3에 있다면 numX[2],numY[3],check[2+3],check2[4-1+2-3] 에 체크를 해주면 된다. 백트래킹을 통해서 경우의수를 세어주면 된다. #include using namespace std; int N;//N 1~14 bool numX[16],numY[16]; int cnt; int check[31],check2[31]; // 4퀸 /방향 대각선 x+y=0,1,2,3,4,5,6,7 \ 방향 대각 N-1 +x-y= 7,6 v.. 2022. 3. 19.
[백준] 9095 1, 2, 3 더하기 c++ 처음에 보자마다 dp라는 것도 몰랐고..^^ 규칙 찾는것도 오래 걸렸다. 2부터 dp를 사용하려고 했던것이 문제였다. 1,2,3 을 구해놓고 해야했던것.. 이렇게 저렇게 해봤는데 중복되는 조합이 생겨서 해맸다. 결론은 n-1경우의 수 +1 ex) n=4 3 +1 , 1 2 +1 , 2 1 + 1 , 1 1 1 +1 4개 n-2경우의 수 +2 1 1 +2 , 2 + 2 2개 n-3경우의 수 +3 1 + 3 1개 으로 구하면 된다. #include using namespace std; int num[12]; // 처음에 문제 보고 어떻게 풀어야하지 고민하다가 알고리즘 분류를 봤는데 dp.. 생각을 못했다. int main() { int T; cin >> T; num[1] = 1; num[2] = 2; num.. 2022. 3. 19.
[백준] 11399 ATM c++ 처음에 운영체제에서 배웠던 프로세스 대기 시간 계산하는 거 생각나서 어렵게 생각했다. 줄서는 사람이 언제 줄 서기 시작했는지 조건이 없기 때문에 쉬웠다. 돈 인출하는데 시간이 적게 걸리는 순으로 줄을 서면 된다! #include #include using namespace std; int n; int person[1001]; //들어오는 시간을 고려하지 않아도 되어서 쉬웠던 문제 int main() { cin >> n; for (int i = 0; i > person[i]; } sort(person, person + n); int sum = 0,ans=0; for (int i = 0; i < n; i++) { sum =(sum+ person[i]); ans += sum; }.. 2022. 3. 17.

티스토리툴바