본문 바로가기

BOJ

Baekjoon 17143 낚시왕 2019. 4. 18. Link https://www.acmicpc.net/problem/17143 소스결과 2212 KB / 760 ms 언어 C++ 17 출처 Baekjoon 분류 시뮬레이션 설명 낚시왕이 낚시를 하며 잡은 상어 크기의 총합을 출력해주자. 시뮬레이션의 정석이라는 생각이 든 문제. 낚시왕은 1부터 가로의 끝까지 천천히 한칸씩 움직인다. 상어는 바라보고 있는 방향으로 자신의 속도만큼 움직인다. 벽에 부딪히는 상황이 오면 상어는 방향을 바꿔 남은 거리만큼 움직인다. 가장 까다로웠던게 마지막 조건이었다. 한 칸에 여러 상어가 있을 수 있고, 그 경우에는 가장 큰 상어가 나머지 상어를 잡아먹는다. 상어의 크기에는 변함이 없다. 낚시왕은 낚시에 성공 할 수도 있지만, 잡지 못하는 경우도 있다. 낚시왕이 움직여 낚시를 ..
Baekjoon 5670 휴대폰 자판 2019. 4. 15. Link https://www.acmicpc.net/problem/5670 소스결과 83284 KB / 596 ms 언어 C++ 17 출처 Baekjoon, Latin America Regional Contests 2012 C번 분류 트라이 설명 핸드폰의 자동 완성 기능과 비슷한 프로그램을 만들었을 때 평균 몇 회의 시도를 해야하는지 출력하자. 여러 문자열을 처리 해야하는 문제다. 앞서 풀었던 문제는 정적으로 처리 했던 것과는 다르게 동적 메모리가 필요하다. 트라이를 정적 메모리로 잡고 있기에는 메모리 낭비가 너무 심하다. 각 자리의 도메인이 소문자이기 때문에 트라이의 차수는 소문자 갯수인 26 사실 트라이를 구성 하는거 까지는 오래 안걸렸는데. 결과값으로 유도하기 위한 부분에서 생각이 좀 필요했다. 트..
Baekjoon 16236 아기상어 2019. 4. 12. Link https://www.acmicpc.net/problem/16236 소스결과 1988 KB / 4 ms 언어 C++ 17 출처 Baekjoon 분류 BFS, 시뮬레이션 설명 작고 귀여운 아기상어가 혼자 힘으로 물고기를 먹으며 얼마나 있는지 출력해주자. 삼성 A형 출제 문제 답게 문제를 열심히 읽어야한다. 다시 한번 더 느꼈다. 먼저 주어진 조건을 생각해보면 - 아기 상어는 자신의 몸집보다 작은 물고기만 먹을 수 있다. - 아기 상어는 자신의 몸집보다 작거나 같은 물고기만 지나갈 수 있다. - 아기 상어는 자기 몸집만큼 물고기를 먹으면 몸집이 커진다. - 아기 상어가 물고기를 먹으면 그 자리는 빈 칸이 된다. - 먹을 수 있는 물고기가 여러마리라면 상단, 상단 중 여러마리라면 좌측이 우선순위가 높..
Baekjoon 1080 행렬 2019. 4. 1. Link https://www.acmicpc.net/problem/1080 소스결과 1992 KB / 0 ms 출처 Baekjoon 언어 C++ 17 분류 그리디 알고리즘 설명 0과 1로 이루어진 행렬 A B에 대해서 특정 연산을 통해 A를 B로 바꾸는 연산의 최솟값을 구하는 프로그램을 만들자. 처음에는 이 문제가 왜 그리디 알고리즘인지 궁금했다. 질문 게시판에는 이미 같은 생각을 가진 다른사람이 있었다. 0,0을 뒤집을 수 있는 경우는 0,0에서 연산을 하는 경우밖에 없다. 따라서 특정 위치는 뒤집을 수 있는 경우의 수가 9보다 작은 경우가 존재한다. 0,0 부터 가로로 확인하면서 뒤집는 수와, 세로로 확인하면서 뒤집는 수를 구해, 둘중에 한군데라도 가능하다면 결과값을 비교해 출력한다. 알고리즘 1. ..
Baekjoon 17103 골드바흐 파티션 2019. 4. 1. Link https://www.acmicpc.net/problem/17103 소스결과 3276 KB / 12 ms 출처 Baekjoon 언어 C++17 분류 수학, 정수론 설명 골드바흐의 추측 : 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다. 를 만족하는 경우의 수를 출력해주자. 소수를 구하기 위한 에라토스테네스의 체를 이용하면 된다. 두 소수가 같아도 된다. 알고리즘 1. 에라토스테네스의 체를 이용하여 소수를 구한 후 저장한다. 2. TC의 개수와 TC를 입력받는다. 3. 각각의 TC에 대하여 가장 작은 소수 부터 반복을 진행한다. 3 - 1. TC의 값에서 소수를 뺸 값이 소수라면 결과값을 1 증가시킨다. 3 - 2. 현재 소수의 값이 TC보다 커질 때 까지 반복한다. 소스코드 #include..
Baekjoon 6588 골드바흐의 추측 2019. 4. 1. Link https://www.acmicpc.net/problem/6588 소스결과 3276 KB / 24 ms 출처 Baekjoon 언어 C++ 17 분류 수학, 정수론, 에라토스테네스의 체 설명 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있는지를 검증하는 프로그램을 작성한다. 두 홀수 소수의 합을 구하기 위해서는 일단 소수를 구해야 한다. 에라토스테네스의 체를 이용하여 소수를 구한다. 짝수인 소수는 2 단 한개밖에 없다. 출력에 있어 b - a가 가장 큰 것을 출력 한다는 말은 a가 가장 작은 수인 경우면 된다. 2개의 조건에 유의해서 문제를 해결한다. 알고리즘 1. 1 ~ 100만 사이의 소수를 전부 구한 후 특정 배열에 저장한다. 2. 입력 값에 대해서 3부터 순서대로 입력값을 뺀 ..
Baekjoon 14890 경사로 2019. 4. 1. Link https://www.acmicpc.net/problem/14890 소스결과 2088 KB / 0 ms 출처 Baekjoon 언어 C++ 17 분류 시뮬레이션 설명 N x N 지도가 주어졌을 때 l길이의 경사로를 놓아 지나갈 수 있는 경로의 갯수를 출력해준다. 경사로를 놓기 위해서는 높이의 차이가 1이어야한다. 또한 경사로는 겹쳐서 놓을 수가 없다. 범위를 벗어나서는 안된다. 경사로의 개수는 무제한이다. 위 조건을 만족 하기 위해서 경사로를 놓은 위치를 기억해야한다. 각 줄에 대해서 독립 시행이기때문에 과거의 결과를 저장하면 안됬었다. 세로와 가로가 같은 방식의 알고리즘이지만 한개의 함수로 묶어서 구현하면 생각보다 구현이 복잡해 나눠서 구현했다. BFS/DFS가 없는 순수한 구현 문제이기때문에 ..
Baekjoon 1964 오각형, 오각형, 오각형... 2019. 4. 1. Link https://www.acmicpc.net/problem/1964 소스결과 1988 KB / 36 ms 출처 Baekjoon 언어 C++ 17 분류 수학 설명 그림과 같은 오각형의 점의 개수를 45678로 나눈 나머지를 출력한다. 그림 속 값이 늘어나는 일정한 규칙을 찾자. 과거 도형과 겹치는 부분을 제외하면 길이가 1 늘어난 변이 3개 존재하고 겹치는 점이 2개 존재한다. % 연산자의 특성을 고려해 결과값을 계산해 나가면 된다. 알고리즘 1. n을 입력 받는다. 2. 현재까지의 오각형 점의 수를 45678로 나눈 값 + 이번에 새로 추가된 점의 수 % 45678을 현재 5각형의 수로 정한다. 초기값은 5 3. 출력한다. 소스코드 #include using namespace std; const ..

티스토리툴바