개발세발은 안되요

문제https://www.acmicpc.net/problem/17143 풀이구현으로 풀어주면 된다.다만 조금 유의해서 구현해야 하는 부분이 있는데, 바로 상어를 이동시키는 부분이다. 상어를 이동시킬 때 예를 들어 상어의 속도만큼 for(int i = 0;..)를 이용해 카운트하면, 시간초과가 발생한다. 따라서 연산 횟수를 줄이기 위해 상어의 최종 위치와 최종 방향을 정해두는 것이 필요하다.(상어가 몇 번 모서리에 부딪힐지를 모르기 때문에!) 일단 상어가 현재 위치까지 돌아오는 "주기"를 확인한다.int mod; // 주기를 저장할 변수if (d == 1 || d == 2) { // 위아래로 움직이는 경우 mod = (R - 1) * 2;} else { // 좌우로 움직이는 경우 mod =..

문제https://www.acmicpc.net/problem/15683 풀이백트래팅 + 생구현으로 문제 풀었다.이 문제에서는 각 카메라를 돌릴 수 있는 모든 조합을 고려해서 사각지대의 수를 카운트해야 한다. 즉 각 카메라 각도의 조합을 이용해야 하기 때문에 재귀+백트래킹을 이용했다.나머지는 정말 구현이다.. 1~5번의 카메라는 결국 상하좌우 중 특정 방향의 조합으로만 움직일 수 있다.int dy[] = {0,0,1,-1}; int dx[] = {1,-1,0,0}; 특정 방향 d로 카메라가 감시할 때, 감시한 영역을 체크하는 함수를 구현했다.다만 백트래킹을 위해 현재 카메라의 d방향의 감시 영역의 체크 표시를 다시 지워주어야 하기 때문에, 현재 체크한 위치 배열을 반환하도록 함수를 구현했다.ve..

문제https://www.acmicpc.net/problem/1182 풀이백트래킹을 이용해 푼다.arr[]에 수열을 입력받고, used[]에 부분수열에 포함시킬 원소들을 표시해가며 표시한 원소의 합이 m이 될 때마다 카운트한다. 이때 부분수열이기 때문에, 숫자들간의 순서는 유지되어야 한다. 즉 각 부분수열 원소의 index는 뒤집히면 안된다. 코드#include using namespace std;int n,m, ans;int arr[21];int used[21];void solve(int idx){ int cnt = 0, num = 0; for(int i=1; i> n >> m; for(int i=1; i> arr[i]; solve(1); cout

문제https://www.acmicpc.net/problem/15651 풀이이번에도 N과 M 문제이다.단, 이번에는 같은 수를 여러번 골라도 되는 수열이다.따라서 기존에 어떤 수를 중복으로 이용하는 것을 막기 위해 사용했던 used[] 배열을 이용할 필요가 없다. 코드 #include using namespace std;int n, m;int arr[10];void solve(int cnt){ if(cnt == m){ for(int i=0; i> n >> m; solve(0); return 0;}

문제https://www.acmicpc.net/problem/15650 풀이기존 N과 M(1)에 조건에 하나 더 붙었다.출력되는 수열은 오름차순이어야 한다.즉 출력되는 수열도 오름차순이어야 하고, 각 수열 역시 오름차순 수열이어야 한다. 이를 위해 나는 이번 cnt에 저장할 i값과 이전에 저장한 arr[cnt-1]의 값을 비교하여,i가 더 큰 경우에만 arr[cnt]에 i를 저장하는 방식으로 풀었다. 코드#include using namespace std;int n, m;int arr[10];int used[10];void solve(int cnt){ if(cnt == m+1){ for(int i=1; i> n >> m; solve(1); return 0;}

문제https://www.acmicpc.net/problem/15649 풀이백트래킹으로 푼다... 코드#include using namespace std;int n, m;int arr[10];int used[10];void solve(int cnt){ if(cnt == m){ for(int i=0; i> n >> m; solve(0); return 0;} 메모백트래킹을 연습하자...

문제https://www.acmicpc.net/problem/2293 풀이입력받은 동전으로 만들 수 있는 모든 값을 조사하며 만들 수 있는 방법을 count 한다. 점화식은 다음과 같다.int cur = coin[i]; // i번째 코인의 값dp[j+cur] +=dp[j]; // j+cur 을 만들 수 있는 방법의 수 = dp[j+cur] = dp[j] 에 현재 동전을 추가한 방법 하나만 추가하면 됨. 코드#include using namespace std;int n, k;int coin[101];int dp[10001];int main() { cin >> n >> k; for(int i=0; i> coin[i]; } for(int i=0; i

문제https://www.acmicpc.net/problem/15886 풀이입력받은 배열에서 E -> W 로 바뀌는 구간이 몇 개인지를 카운트한다. 코드#include using namespace std;int n, ans;char c[1000];int main() { cin >> n; for(int i=0; i> c[i]; } //visited를 모두 방문하기까지 얼마나 걸리는지를 체크 char flag = c[0]; for(int i=1; i