presentLee

https://www.acmicpc.net/problem/6603 처음 푼 방문여부 배열로 체크하며 검사한 풀이 출력 조건만 보고 오름차순 조건과 방문여부 배열을 추가했지만 입력 조건에 원소가 오름차순으로 주어진다는 것을 확인하고 하단에 풀이를 추가 #include #include #include #include #include #include using namespace std; int arrsize; int arr[13]; int prarr[13]; bool check[13]; void back(int prev, int size); int main() { cin >> arrsize; while (arrsize != 0) { memset(check, 0, sizeof(check)); for (int i..

baekjoon 2024. 2. 26. 23:53

https://www.acmicpc.net/problem/1759 목록에서 필요한 갯수만큼 조건에 맞춰 탐색해 뽑아낸다. 백트래킹 사용해야 했던 문제 #include #include #include #include using namespace std; char str[20]; char arr[20]; int l, c; bool check[26]; void dfs(int index, int count); int main() { memset(check, 0, sizeof(check)); check[0] = check[4] = check['i' - 'a'] = check['o' - 'a']= check['u' - 'a'] = 1; cin >> l >> c; for (int i = 0; i < c; i++) {..

baekjoon 2024. 2. 19. 05:19

https://www.acmicpc.net/problem/1697 dp 문제라고 생각하고 풀다가 답이 안나와서 분류를 봤다. bfs로 풀 수 있는 문제였다. 이런느낌으로 연결된 그래프를 연상했다. dfs로 사용하면 모든 경우를 끝까지 가봐서 가장 작은 것을 선택 해야 겠지만 bfs를 사용 시에 같은 횟수로 먼저 도착했을 때 가장 최소 비용을 사용했다고 확인할 수 있으니 bfs를 사용. #include #include #include #include #include #include struct forq { int num; int count; }; using namespace std; bool check[100005]; int linenum, verticenum; int subin, sister; void ..

baekjoon 2024. 2. 18. 03:05

숫자 이차원 배열에서 1로 저장되어있는 덩어리를 찾아내서 처리하는 문제. 이차원 배열을 훑어 나가다가 1로 저장되어있고 방문한 적 없다면 dfs를 활용해서 해당 묶음을 한번에 처리하는 식으로 구현한다. #include #include #include #include #include #include #include using namespace std; int arr[26][26]; bool check[26][26]; int n; int housecount; int d = 0; priority_queue numlist; void dfs(int row, int col); int main() { string temp; cin >> n; for (int i = 0; i > temp;..

카테고리 없음 2024. 2. 17. 21:35

탑다운, 바텀업 방식 첨부 세가지 조건을 합쳐보면 결국 한 집 기준으로 좌 우 집이랑 같은 색이 안된다는 말. 빨 파 빨 파 빨 파 빨 파 이런식으로 존재해도 조건은 만족한다. 어떤 위치의 집이 어떤 색일때의 경우를 따져 보아야 최소 비용을 구할 수 있을 것이기에 dp를 사용한다. Top down 방식 풀이 #include #include #include #define BIGNUM 2100000000 using namespace std; struct house { int r; int g; int b; }; int inputnum; house arr[1001]; int dp[1001][3];// 0=r 1=g 2=b int rec(int index, int num, int check); int main()..

카테고리 없음 2024. 2. 17. 20:38

탑다운방식과 바텀업 방식 첨부. 삼각형 형태로 구성된 수를 한칸씩 타고 내려오며 총 합이 가장 큰 경로의 합을 찾는 문제 얼핏 보면 그리디로 풀 수도 있을 것 같지만 좌측처럼 그리디하게 당장 큰 것을 찾아 내려가면 실제로 가장 큰 경로가 되지 않는다. 많은 경우의 수를 비교하기 위해 dp를 사용해서 풀어야 했던 문제. 맨 위칸 값을 기준으로 시작해서 다음행의 같은열과 다음 열 값을 확인 해 더 큰 값을 dp에 저장한다. 마지막 행에 도달하면 해당 위치의 값을 그대로 반환해주면 될 것이다. top-down 방식 풀이 #include #include #include #include using namespace std; int arr[501][501]; int dp[501][501]; int inputnum;..

baekjoon 2024. 2. 17. 20:26

2*n 크기의 직사각형에 1*2 세로로 긴 직사각형과 2*1 가로가 긴 직사각형으로 채울 수 있는 방법을 우선 찾는다. 2*n에서 n이 커질수록 가로로 한칸이 길어진다. 채울 수 있는 것은 1*2나 2*1 사각형이므로 가로가 한칸 길어지면 1*2를 하나 넣을 수 있다. 3에서 4로 넘어갈때 파란색 테두리를 친 사각형들이 그 예시. 가로 길이가 n-2 인 경우에서 2*1을 위아래로 하나씩 배치해서 가로길이 n을 만드는 경우도 존재한다. (초록색테두리) 가로 길이가 n인 직사각형은 n-1길이의 직사각형갯수와 n-2길이의 직사각형 갯수를 합한 값이라는 결과 추론 가능. 피보나치 수열의 형태를 띄고 있으므로 dp 사용. #include #include #include using namespace std; lon..

baekjoon 2024. 2. 17. 00:24

경우의 수가 많다. dp문제로 보이므로 규칙을 찾을때까지 적어본다. 각 숫자를 1,2,3의 합으로 구하는 방법을 쭉 적어보다가 규칙을 발견할 수 있었다. 4부터 보게되면 네모를 친 1+1+1+1, 2+1+1, 1+2+1, 3+1은 4보다 1 작은 3의 네가지 경우의 수의 뒤에 1을 더한 형태 세모를 친 2+2, 1+1+2의 경우에는 4보다 2 작은 2의 2가지 경우의 수의 뒤에 2를 더한 형태 역삼각형의 경우는 4보다 3 작은 1의 1가지 경우의 수의 뒤에 3을 더한 형태다. dp[i]=dp[i-1]+dp[i-2]+dp[i-3] 피보나치수가 생각나는 형태의 점화식을 찾을 수 있었다. #include #include #include using namespace std; long long dp[12]; lo..

baekjoon 2024. 2. 16. 23:02