알고리즘 풀이
-
백준(BOJ) 3190번 뱀알고리즘 풀이/백준(Boj) 2019. 9. 15. 02:05
문제 : https://www.acmicpc.net/problem/3190 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.만약 이동한 칸에 사과가 없다면, 몸..
-
POLY 폴리오미노 :: 알고스팟알고리즘 풀이/알고리즘 해결전략 연습 2019. 9. 13. 00:52
문제 : https://algospot.com/judge/problem/read/POLY 문제정사각형들의 변들을 서로 완전하게 붙여 만든 도형들을 폴리오미노(Polyomino)라고 부릅니다. n개의 정사각형으로 구성된 폴리오미노들을 만들려고하는데, 이 중 세로로 단조(monotone)인 폴리오미노의 수가 몇 개나 되는지 세고 싶습니다. 세로로 단조라는 말은 어떤 가로줄도 폴리오미노를 두 번 이상 교차하지 않는다는 뜻입니다.예를 들어 그림 (a)는 정상적인 세로 단조 폴리오미노입니다. 그러나 (b)는 점선이 폴리오미노를 두 번 교차하기 때문에 세로 단조 폴리오미노가 아닙니다. (c)는 맨 오른쪽 아래 있는 정사각형이 다른 정사각형과 변을 완전히 맞대고 있지 않기 때문에 폴리오미노가 아닙니다.n개의 정사각형..
-
백준(BOJ) 15686번 치킨 배달알고리즘 풀이/백준(Boj) 2019. 9. 12. 18:37
문제 : https://www.acmicpc.net/problem/15686 문제크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는..
-
백준(BOJ) 17140번 이차원 배열과 연산알고리즘 풀이/백준(Boj) 2019. 9. 11. 02:23
문제 : https://www.acmicpc.net/problem/17140 문제크기가 3×3인 배열 A가 있다. 1초가 지날때마다 배열에 연산이 적용된다.R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 = 열 이라면 행을 아니라면 열을 탐색하자. 탐색시 vector 를 통하여 나온숫자 횟수, 숫자 로 담은후 오름차순 정렬해서 second , first 순으로 할당해주자. 행 or 열에 탐색이 한번끝났다면 가장 큰 행 or 열의 수를 기억해놨다가 행이라면 열을 열이라면 행을 그 수로 바꿔주자. 코드 ( C ++ ) #include #include #include #include usin..
-
백준(BOJ) 12865번 평범한 배낭알고리즘 풀이/백준(Boj) 2019. 9. 10. 01:49
문제 : https://www.acmicpc.net/problem/12865 문제이 문제는 아주 평범한 배낭에 관한 문제이다.한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K무게까지의 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자. 풀이 :W와 V배열을 별도로 만들어서 저장한다. 그 후 두가지 경..
-
백준(BOJ) 1783번 병든 나이트알고리즘 풀이/백준(Boj) 2019. 9. 8. 16:48
문제 : https://www.acmicpc.net/problem/1783 문제병든 나이트가 N * M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다.2칸 위로, 1칸 오른쪽1칸 위로, 2칸 오른쪽1칸 아래로, 2칸 오른쪽2칸 아래로, 1칸 오른쪽병든 나이트는 병들었지만, 그래도 명색이 체스 나이트이기 때문에 많은 칸을 방문하고 싶어 한다. 병든 나이트의 이동에는 제약이 있다. 만약, 이동 횟수가 4번 이상인 경우에는 위의 이동 방법을 각각 한 번 이상 이용해야 한다.체스판의 크기가 주어졌을 때, 병든 나이트가 방문할 수 있는 칸의 최대 개수를 출력하는 프로그램을 작성하시오. 처음에 있는 칸도 센다. 풀이 : 세로가 1이거나 ..
-
캐나다 여행 :: 알고스팟알고리즘 풀이/알고리즘 해결전략 연습 2019. 9. 8. 01:12
문제 : https://algospot.com/judge/problem/read/CANADATRIP 문제동건이는 여름 방학을 맞아 자동차를 끌고 캐나다 횡단 여행을 떠나기로 했습니다. 캐나다의 1번 고속도로는 세계에서 가장 긴 고속도로 중 하나로, 캐나다의 동쪽 끝에서 서쪽 끝까지 있는 모든 주요 도시를 연결합니다. 동건이는 이 고속도로를 타고 캐나다의 서쪽 끝 빅토리아에서 동쪽 끝 세인트 존까지 8,030km 를 달리기로 마음먹었습니다.이 고속도로는 굉장히 많은 표지판이 있기로도 유명합니다(이 문장부터는 사실이 아닙니다..). 이 고속도로는 N개의 주요 도시를 지나치는데, 각 도시까지의 남은 거리를 나타내는 표지판이 많기 때문입니다. i번째 도시까지의 거리를 나타내는 표지판은 도시에 도착하기 Mi미터 ..