1일1알

https://www.acmicpc.net/problem/17143 상어가 계속 움직이고 있는 상태에서 상어 낚시꾼이 오른쪽으로 움직이면서 잡을 수 있는 상어의 총 크기를 구하는 문제이다. Shark 클래스를 만들어서 상어의 크기, 속도, 움직이는 방향 등을 저장하고 관리하기 위해 입력받은 순서대로 Id를 부여하였다.클래스 내에 Move, Caught 멤버함수를 구현하여 상어가 움직이거나 잡혔을때 행동을 작성하였다. 1. 낚시꾼이 움직인다.2. 낚시꾼이 있는 열에서 땅에서 가장 가까운 상어를 잡는다.3. 상어가 움직인다. 위의 순서대로 동작한다. 낚시터의 격자에 상어의 Id로 상어의 위치를 표시했고, 낚시꾼이 움직이다가 상어를 잡을 수 있는 상황이면 Id로 상어의 정보를 찾아서 Shark::Caught함..

https://www.acmicpc.net/problem/1799 대각선으로만 이동할 수 있는 비숍 말들을 영역이 겹치지 않게 배치할 수 있는 최대의 수를 구하는 문제이다.처음에 배치할 수 있는 영역은 제한되어있고, 배치를 못하는곳에 움직이는 것은 가능하다. 우선 직관적으로 백트래킹으로 접근하여 배치가 가능한 영역들을 저장하고 저장한 영역들에 대해 백트래킹을 돌려주었다.한번 배치한 영역은 4가지 대각선 방향에 다른 말이 배치할 수 없도록 표시를 해두고 저장해뒀다가, 돌아올때는 표시한 영역들을 다시 원상태로 돌려주었다. 하지만 역시 골드1이라그런지 이런 단순한 방법으로는 풀리지 않았고 시간초과가 났다. 계속 생각해봤는데도 마땅한 방법이 생각나지 않아서 질문 게시판을 한번 들어가봤는데 흑색과 백색으로 나누라..

https://www.acmicpc.net/problem/1766 어떤 문제를 풀기전에 풀어야 하는 문제가 있기 때문에 이에 적합한 위상정렬을 사용해서 문제를 해결하였다.그리고 번호가 낮은 문제부터 풀어야 하기 때문에 위상정렬에서 사용하는 큐를 우선순위 큐로 바꾸고 낮은 번호부터 뽑히도록 하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;using int64 = long long;vector> graph;vector inDegree;int main() { ..

https://www.acmicpc.net/problem/9328 크게 보면 단순 bfs 구현 문제인데, 어떤 열쇠가 있어야 특정 문을 열 수 있고, 맵 밖으로 나갔다고 끝이 아니라 다른 외곽 지역으로 들어올 수 있다는 추가 조건이 있는 문제이다. 우선 방문 표시를 할때 단순히 true, false로 표시하면 안된다.어떤 열쇠를 보유하지 않고 특정 문에 도달했을때와 보유한 상태에서 도달했을 때 차이가 있기 때문이다.그래서 비트연산을 이용해서 어떤 열쇠들을 가진 상태로 방문했는지를 표시하였다.예를들어 a열쇠와 c열쇠가 있다면 101(cba)이고 10진수로 변환하면 5가 된다.이렇게 하면 정수 하나로 어떤 열쇠들을 가지고 방문했는지 표시할 수 있다. 그리고 어떤 열쇠를 가지고 있는지 확인할 수 있어야 한다...

https://www.acmicpc.net/problem/27172 다른 수와 비교하여 내가 다른 수의 약수이면 1점을 얻고, 내가 다른 수의 배수이면 1점을 잃는 게임이다.n이 최대 10만이기때문에 두개씩 짝지어서 전부 비교하면 시간초과가 날 것이기 때문에 다른 방법을 사용해야 한다. 모든 수를 순회하며 약수를 구하고, 약수를 순회하며 만약 약수가 다른 카드에 존재하면 해당 카드는 1점을 얻고 본인은 1점을 잃는다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace st..

https://www.acmicpc.net/problem/20529 n이 10만까지 들어올 수 있기 때문에 하나씩 다 둘러보면 시간초과가 나기때문에 다른 방법을 생각해야 한다.MBTI는 종류가 한정되어있기때문에 입력받은 MBTI중 2개씩 짝을 짓고 n만큼 순회하면최대 16 * 16 * 100000으로 모든 경우를 순회할 수 있다.물론 입력받은 MBTI가 1개인데 셋다 같은 MBTI일수는 없기때문에 그런 부분에 대해서는 예외처리를 해주었다.#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using n..