kimtetris 님의 블로그

문제 https://www.acmicpc.net/problem/15989 풀이dp에 저장되는 각 숫자의 0번 배열에는 1이 사용된 경우, 1번 배열에는 1이 사용되지 않고 2가 포함된 경우, 2번 배열에는 3만 사용된 경우들의 개수를 저장했습니다. 이런 규칙을 통해서 개수를 정하기 때문에 0번 배열 - 이전 숫자에서 사용했던 모든 경우에 1을 더함 1번 배열 - 현재 숫자 - 2에서 1이 사용된 경우를 제외한 2와 3만 사용한 경우 2번 배열 - 현재 숫자 - 3에서 3만 사용된 경우 3가지의 경우를 모두 더하면 해당 숫자에서 나오는 모든 경우의 수를 구할 수 있습니다. ...for (int i = 4; i 전체 코드#include using namespace std;i..

문제https://www.acmicpc.net/problem/1918 풀이스택을 이용해서 특정 조건에 맞는다면 계속해서 스택의 top을 출력해 주면 문제를 해결할 수 있었습니다. 문제의 규칙은 다음 4가지입니다. 1. 숫자는 바로 출력 2. ( 은 무조건 push 3. ) 라면 스택에서 ( 가 나올 때까지 pop 4. 현재 스택의 top이 자신보다 연산 우선순위가 높거나 같을 경우 pop [ 즉, *, / 라면 *와 / 일 때 pop 및 출력, +, - 일 때는 +, -, *, / 전부 pop 및 출력 ] 1번 조건의 경우 마지막에 else를 통해 바로 출력하도록 했습니다. ...else cout 2번과 3번의 조건의 경우 ( 일땐 push, ) 일 땐 스택의..

문제 https://www.acmicpc.net/problem/2749 풀이문제를 보고 전혀 감이 안 잡혀서 선행 문제인 피사노 주기 문제를 풀고 왔습니다.https://kimtetris.tistory.com/entry/BOJ-%EB%B0%B1%EC%A4%80-9471-%ED%94%BC%EC%82%AC%EB%85%B8-%EC%A3%BC%EA%B8%B0-c-%EC%88%98%ED%95%99-%EB%B6%80%EB%A3%A8%ED%8A%B8%ED%8F%AC%EC%8A%A4-%EC%A0%95%EC%88%98%EB%A1%A0 [BOJ] 백준 9471 피사노 주기 c++ (수학, 부루트포스, 정수론)문제https://www.acmicpc.net/problem/9471 풀이문제에 보면 뭔가 다양한 성질들이 있..

문제https://www.acmicpc.net/problem/9471 풀이문제에 보면 뭔가 다양한 성질들이 있지만 거두절미하고 표와 같이 피보나치수열을 특정 수로 나누면 나머지에 규칙이 있다는 것만 이해하면 충분했습니다. 핵심 알고리즘은 간단하게 피보나치수열을 진행하면서 m으로 나누고, 현재 수와 다음 수가 0, 1 즉 반복되기 시작하는 상황이 보이면 멈추는 방식으로 구현했습니다. 대신 피보나치수열을 진행할 때 중간 과정에서 m으로 나눠주지 않으면 메모리 초과가 일어난다는 점int picano(int m){ int m1 = 1, m2 = 1, cnt = 1, tmp; while (m1 != 0 || m2 != 1) { cnt++; tmp = (m1 + m2..

문제 https://www.acmicpc.net/problem/1655 풀이우선순위 큐를 하나만 사용해서 풀려다 시간초과가 나 다른 블로그를 참고했습니다https://velog.io/@rhkswls98/%EB%B0%B1%EC%A4%80-1655-C-%EA%B0%80%EC%9A%B4%EB%8D%B0%EB%A5%BC-%EB%A7%90%ED%95%B4%EC%9A%94 풀이 과정은 우선순위 큐를 2개로 분할해서 사용한다는 아이디어만 있다면 생각보다 간단했습니다. 1. 최대 큐와 최소 큐의 크기가 같다면 무조건 최대 큐에 값을 넣습니다. 2. 최대 큐 크기가 더 크다면 최소 큐에 값을 넣습니다. 3. 값을 삽입 후 각 큐의 top값을 확인했을 때 최대 큐가 크다면 값을 교환합니다. 3번의 경우 문..

문제https://www.acmicpc.net/problem/20055 풀이과정 1번은 트레일러와 로봇들의 위치를 구분해서 구현했습니다. "내리는 위치"는 도착하자마자 무조건 내리고, 1번 칸의 경우엔 새로 올라오기 때문에 0으로 만들어줬습니다. int tmp = dq.back();dq.pop_back();dq.push_front(tmp);for (int i = n - 1; i > 0; i--){ robot[i] = robot[i - 1];}robot[0] = 0, robot[n - 1] = 0; 과정 2번은 "내리는 위치" 이전 칸부터 뒤에서 앞으로 검사해나가며 조건에 맞는 경우에 로봇들이 한칸씩 움직이는 것을 구현했습니다. 그리고 움직인 경우엔 컨테이너의 내구도를 검사해줬습니다. for (..

문제 https://www.acmicpc.net/problem/1202 풀이먼저 보석들을 저장한 배열과 가방의 크기를 저장한 배열을 작은 값부터 오름차순으로 정렬해 줍니다. 그리고 정답을 저장할 변수는 long long으로 하지 않으면 int의 범위를 넘어 틀립니다. 작은 수 부터 구하는 이유는 priority_queue를 사용해서 현재 가방에 넣을 수 있는 보석 중 가장 가치가 높은 것을 구하기 위해서입니다. pair info[300001];int bag[300001];priority_queue pq;long long ans;...sort(info, info + n);sort(bag, bag + k);... 다음으로 가방을 기준으로 탐색을 시작합니다. 가장 작은 가방을 선택하고, 그 가방에 들어갈..

문제https://www.acmicpc.net/problem/1865 풀이벨만-포드 알고리즘의 경우 주로 그래프 이론에서 음수인 가중치가 있을 때 사용하는 알고리즘입니다. 그래서 문제를 읽자마자 벨만-포드 알고리즘을 써야 된다는 것을 알았습니다. 사용 배열은 모든 간선을 한 번에 돌기 때문에 1차원 벡터를 선언해주고, 현재까지 값을 저장할 배열을 선언했습니다. 일반 길의 경우엔 방향이 없어 양쪽을 모두 넣어주고, 워프는 단방향이기에 가중치를 음수로하여 저장했습니다. vector, int>> v;int dis[501];...v.push_back({{s, e}, t});v.push_back({{e, s}, t});......v.push_back({{s, e}, -t});... 어떤 간선에서 시작해도 결..

문제https://www.acmicpc.net/problem/16236 풀이먼저 이동할 상어의 위치를 저장할 shark, bfs에 사용할 visit과 상어의 크기, 먹이를 먹은 횟수를 저장할 변수를 선언했습니다. int sea[21][21], visit[21][21];vector> shark;int dx[4] = {0, -1, 1, 0};int dy[4] = {-1, 0, 0, 1};int ans = 0, size_shark = 2, cnt = 0; 다음으로는 큰 사이클입니다. 상어가 한 번의 먹이를 먹는 것을 하나의 사이클로 잡아 구현했습니다. 여기에 사이클을 진행하면서 먹이를 먹는 것과, 몸집을 불리는 것을 추가했습니다. 그리고 memset을 이용해 방문 여부를 계속 초기화해 줬습니다. whil..

문제 https://www.acmicpc.net/problem/16235 풀이deque를 사용하여 심어져 있는 나무들을 저장했습니다. int food[10][10];int ground[10][10];deque tree[10][10];int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};int dy[8] = {1, 1, 0, -1, -1, -1, 0, 1}; 칸마다 다르게 작동하기 때문에 봄과 여름을 한 번에 처리했습니다. 봄은 단순히 땅에 남아있는 영양분과 나무의 나이를 비교하여 자랄 수 없는 경우엔 cnt로 개수를 저장했습니다. 그런 후 여름은 나무들이 나이순으로 저장되어 있기 때문에 뒤에서부터 cnt값만큼의 나무들을 양분으로 바꿨습니다. int cnt = 0;for (int l..