BOJ
-
[2670] 연속부분최대곱BOJ 2021. 10. 12. 00:27
https://www.acmicpc.net/problem/2670 2670번: 연속부분최대곱 첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나 www.acmicpc.net i번째 수를 하나씩 확인한다고 생각할때, 지금까지(i-1까지) 곱해온것에 현재(i)를 곱한것이 더 크다면 곱하고, 아니라면 현재의 수로 유지한다. 정답을 그때그때 최대값으로 갱신해둔다면, 정답이 어디있는지를 찾을필요없이 바로 출력할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include using namespace std;..
-
[15489] 파스칼 삼각형BOJ 2021. 10. 12. 00:13
https://www.acmicpc.net/problem/15489 15489번: 파스칼 삼각형 첫째 줄에 양의 정수 R, C, W가 공백을 한 칸씩 두고 차례로 주어진다. (단, 2 ≤ R+W ≤ 30, 2 ≤ C+W ≤ 30, 1 ≤ W ≤ 29, C ≤ R) www.acmicpc.net 행과 열, 2개의 상태로 위치가 구분되므로 2차원 dp를 생성한다. 시각적으로 보이는걸 수식으로 구체화해보면, dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] 이다. 정삼각형은 2중for로 구성할 수 있는데, 초기값은 각각 r과 c로, 입력받은 그대로 넣어주면 되지만 조건문의 경우 조금 더 신경써줄 부분이 존재하는데... i가 바깥, j가 안쪽의 for문으로, 총 2중for라 할때 조건문..
-
[22869] 징검다리 건너기 (small)BOJ 2021. 10. 12. 00:00
https://www.acmicpc.net/problem/22869 22869번: 징검다리 건너기 (small) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으 www.acmicpc.net O(N^2)으로 풀이가 가능하므로 조건만 잘 구현해주면 간단히 해결할 수 있는 문제이다. 필요한것은 이동이 가능한지에 대한 true혹은 false의 값일 뿐이므로 dp[]를 bool형으로 선언해주고, 초기상태를 dp[1] = true; 로 표현해주었다. 이후로는 시작점을 의미하는 큰 for()와 도착점을 의미하는 작은 for()를 돌려서..
-
[21317] 징검다리 건너기BOJ 2021. 10. 11. 23:43
https://www.acmicpc.net/problem/21317 21317번: 징검다리 건너기 산삼을 얻기 위해 필요한 영재의 최소 에너지를 출력한다. www.acmicpc.net N이 작아 브루트포스로 해결이 가능하다. 현재 상태를 나타낼때 필요한것은 아래와 같다. int i : 위치 bool flag : 매우 큰 점프를 사용한적이 있는지 int cost : 현재까지의 비용 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include using namespace std; int n, k, ans = 987654321, a[21][2]; void f(int i, bool flag, int cost) { if (i > n) return; i..
-
[22857] 가장 긴 짝수 연속한 부분 수열 (small)BOJ 2021. 10. 11. 23:28
https://www.acmicpc.net/problem/22857 22857번: 가장 긴 짝수 연속한 부분 수열 (small) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 투포인터로 해결할 수 있다. 구간 [i, j]에 cnt개의 홀수가 존재한다면, score는 (j - i + 1) - cnt이고, 이것이 구간 [i, j]에서의 최적해이다. 이를 바탕으로 score의 최대값을 투포인터의 탐색과정동안 업데이트해주었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #inclu..
-
[17071] 숨바꼭질 5BOJ 2021. 10. 11. 03:53
https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 일반적인 형태의 bfs로 해결할 수 있었던 [1697]숨바꼭질과 달리, 이 문제는 동생의 위치가 고정적이지 않다. 단순한 bfs로 구현하면 최적해를 찾지 못하거나, 찾더라도 시간초과가 나오는 구조로 되어있는듯 하다. 수빈이가 x+1로 이동하고, 다시 x-1로 이동하게 된다면 최종적으로 2초의 시간을 사용하여 제자리로 돌아오는형태가 된다. 즉, 이 문제에서 연산..
-
[7785] 회사에 있는 사람BOJ 2021. 10. 9. 21:53
https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net set을 사용하여 구현했다. enter인 경우에는 set.insert(), leave인 경우에는 set.erase()로 구현이 가능하며 사전순의 역순으로 출력해야 하므로 내림차순으로 set을 선언해주었다. n줄로 된 쿼리가 끝나면, set을 순회하며 출력해주면 회사에 남아있는 사람을 찾을 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ..
-
[1062] 가르침BOJ 2021. 10. 9. 21:46
https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net TSP문제와 비슷하게 비트마스킹+백트래킹으로 해결이 가능하다. 비트마스크를 사용하지않아도 TLE가 나오는 문제는 아니다. 모든 단어의 시작과 끝이 정해져있다는 문제 조건에 근간하여 a c i n t 5글자를 먼저 배우고 시작을 하도록 구현하면 조금 더 최적화가 되겠다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26..
-
[9184] 신나는 함수 실행BOJ 2021. 10. 8. 22:41
https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 메모이제이션을 사용해보라는 문제로 생각된다. 의사코드를 문제에서 제공했기에, 그대로 옮겨주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include using namespace std; int memo[51][51][51]; int f(int a, int b, int c) { if (a 20) return f(20, 20, 20);..
-
[14456] Hoof, Paper, Scissors (Bronze)BOJ 2021. 10. 8. 01:01
https://www.acmicpc.net/problem/14456 14456번: Hoof, Paper, Scissors (Bronze) You have probably heard of the game "Rock, Paper, Scissors". The cows like to play a similar game they call "Hoof, Paper, Scissors". The rules of "Hoof, Paper, Scissors" are simple. Two cows play against each-other. They both count to three and then each s www.acmicpc.net 1을 기준으로 보면, 1이 이길수 있는 상대가 2가 될수도 있고, 3이될수도 있다. 전..