Problem Solving
-
[BOJ] #3190 _ 뱀Problem Solving/BOJ 2019. 8. 12. 23:14
[뱀] https://www.acmicpc.net/problem/3190 3190번: 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따 www.acmicpc.net 시뮬레이션 문제이다. 알려준 규칙대로 코드를 구현하면 된다. 이동한 칸에 사과가 없을 경우, 꼬리가 위치한 칸을 비워주는 것이 관건이다...
-
[BOJ] #14889 _ 스타트와 링크Problem Solving/BOJ 2019. 8. 12. 23:08
[스타트와 링크] https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net dfs를 이용하는 문제이다. next_permutation을 이용하면 더 쉽게 구현할 수 있지만, {a, a, a, b, b, b}와 {b, b, b, a, a, a}를 중복 계산한다. (단, 중복 계산해도 시간 초과는 발생하지 않기 때문에 사용해도 된다.) 중복 계산하지 않도록 구현하기 위해 아래와 같이 재귀 함수를 이용하여 구현하였다. [ 소스 코드 ] #include #include #inclu..
-
[BOJ] #9465 _ 스티커Problem Solving/BOJ 2019. 8. 12. 22:34
[스티커] https://www.acmicpc.net/problem/9465 9465번: 스티커 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점 www.acmicpc.net 아주 간단한 DP문제이다. 100점인 스티커를 기준으로 가능한 경우는 아래와 같이 3가지다. 이를 이용하여 점화식을 만들 수 있..
-
[SWEA] #5656 _ 벽돌 깨기Problem Solving/SWEA 2019. 8. 4. 10:28
[벽돌 깨기] https://swexpertacademy.com/main/code/problem/problemDetail.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 벡터를 사용하여 벽돌을 세로가 아닌 가로로 저장하고, 가장 끝에 있는 값을 깨는 방법으로 구현하였다. (erase를 사용하여 가운데 값을 삭제해도 앞으로 땡기는 작업을 하지 않기 위해 벡터 사용) 하지만, 직관적으로 보기에는 배열을 이용하는게 좋은 것 같다..;; 깰 수 있는 모든 경우의 수를 다 돌려 가장 벽돌이 적게 남은 경우를 출력하였다. 모든 경우의 수를 하지 않는 방법을 생각하다가,,, 제한 시간이 3초인 것을 보고 모든 경우의 ..
-
[SWEA] #5644 _ 무선 충전Problem Solving/SWEA 2019. 8. 4. 10:17
[무선 충전] https://swexpertacademy.com/main/code/problem/problemDetail.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com bfs를 이용하여 BC의 충전 범위 만큼 성능 값을 맵에 저장한다. 이 때, 사용자는 두명이기 때문에 BC의 가장 큰 두개의 값만 저장하고 있으면 된다. (BC가 4개가 겹칠 경우에 큰 성능 2개를 저장) 미리 맵에 마름모 꼴로 성능 값을 저장해두고, 두명의 사용자가 움직일 때, 맵에 저장된 값을 더해주면서 총 충전량을 구한다. [ 소스 코드 ] #include #include #include #include using namespace ..