본문 바로가기

📊알고리즘/BOJ101

BOJ 3190 - 뱀 https://www.acmicpc.net/problem/3190 구현이 문제에서 크게 구현할 부분은 사과를 먹었을 때 꼬리를 늘리는 작업, 뱀 몸통에 부딪혔을 때 게임이 종료되게 하는 기능 이다.뱀의 위치를 효율적으로 나타내기 위한 자료구조를 생각해내는 것이 핵심이다. 뱀이 한 번 움직이면 꼬리와 머리가 한 칸씩 움직이기 때문에 앞과 뒤를 다룰 수 있는 deque를 이용하면 된다. 문제에서 헤맸던 부분이 방향을 돌리는 시점이다.예를 들어 10초에 왼쪽으로 움직인다는 뜻은 이전 방향으로 10까지 움직인 후에 방향을 바꾼다는 뜻이다! 구현 문제 중 쉬운 편에 속한다. 코드#include #include #include using namespace std;#define UP_DIR 0#define RIGHT.. 2024. 6. 20.
BOJ 18291 - 비요뜨의 징검다리 건너기 18291번: 비요뜨의 징검다리 건너기 (acmicpc.net) 접근 방법도저히 감이 안잡혀서 점근식으로 접근해보았다. N=3 인 경우21 1 N=4 인 경우32 11 21 1 1 N=5 인 경우4 3 1 1 3 2 1 1 1 2 1 1 1 2 2 2 1 1 1 1 2 -> 4 -> 8 -> ...2의 제곱 형태로 나아간다고 생각하여2의 N-2 승을 이용하니 맞았다. 더 자세한 설명은 아래 참고 블로그를 확인해보자.  코드#include #include #include #define ll long longusing namespace std;ll t, n;ll mod = 1000000007;void powFunc(ll a, ll b) { ll res = 1; while(b) { if (b % 2 != 0.. 2024. 5. 1.
BOJ 3109 - 빵집 3109번: 빵집 (acmicpc.net) 접근방법이번 문제는 그래프 탐색을 통해 오른쪽, 오른쪽 대각 위, 오른쪽 대각 아래 이렇게 총 3가지로 이동하며 마지막 열에 도달하는 문제이다.이 과정에서 발생하는 문제는 다음과 같다. 1. 어떻게 하야 가장 많은 파이프가 지나갈 수 있도록 배치할 수 있을까?2. 도착점까지 연결하는 파이프는  하나여야 한다. 먼저 1번부터 해결해보자.예제 1번을 보자 5 5.xx....x..........x....x. 여기서 0,0 에서 출발한 파이프 라인은 최대한 위쪽을 붙어서 이동해야 한다. 5 51xx.1.1x1...1.....x....x.이런게 1의 경로를 따라 이동해야 하므로, 움직이는 순서는 -1, 0 ,1 이어야 한다. (중요) 이제 2번째 문제인 "도착점까지 연결.. 2024. 4. 30.
BOJ 2531 - 회전 초밥 2531번: 회전 초밥 (acmicpc.net) 접근 방법초밥을 연속 K를 먹었을 때, 먹을 수 있는 가장 많은 가짓 수를 선택하는 문제이다.이 문제에서 주의 깊게 봐야할 것이 쿠폰이다. 처음에 쿠폰이 해당 쿠폰의 초밥을 먹을 때, 추가로 1개를 더 먹는 거라고 착각했다.그러나 이 문제에서 " 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다." 를 고려하지 않은 문제풀이이다. 따라서, 해당 쿠폰의 초밥을 안 먹은 경우 가지 수를 1가지 추가하고 슬라이딩 윈도우를 하면 된다. 코드#include #include #include #define ll long longusing namespace std;int n, d, k, c;vector v;int selec.. 2024. 4. 29.
BOJ 2473 - 세 용액 2473번: 세 용액 (acmicpc.net) 2473번: 세 용액첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상www.acmicpc.net 접근 방법용액 문제와 비슷하게 해결 가능한 투 포인터 문제이다.세 용액의 합이 0에 가장 가까운 용액들을 고르는 문제이기 때문에 처음엔 두 개의 용액을 모두 더 한 배열을 이용하여, 나머지 용액을 투포인터로 선정하는 방법을 사용했다.  struct st{ int a; // 용액A int b; // 용액B int sum; // 용액A + 용액B}위 구.. 2024. 4. 23.
BOJ 1644 - 소수의 연속합 1644번: 소수의 연속합 (acmicpc.net) 접근 방법 투 포인터와 소수판별 알고리즘이 혼합된 문제이다. 소수 판별을 하기 위해 에라스토테네스의 체를 이용하여 소수를 배열에 저장한다. 해당 소수 배열을 투포인트를 돌면서 각 연속적인 수들의 합이 N이 될 때, 경우의 수를 + 1한다. 코드 #include #include #include using namespace std; #define MAX 4000001 #define ll long long bool chk[MAX+3]; vector arr; ll n, s; void func() { chk[1] = true; for (int i = 2; i < MAX; i++) { if(!chk[i]) arr.push_back(i); for (int j = i.. 2024. 4. 23.

티스토리툴바