https://www.acmicpc.net/problem/10942 [10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net](https://www.acmicpc.net/problem/10942) DP i부터 j까지의 숫자가 팰린드롬이라는 것을 확인하는 방법은 무엇일까? 만일 i번째 숫자와 j번째 숫자가 같은 경우, i + 1부터 j - 1까지가 팰린드롬이면, i부터 j까지도 팰린드롬이다. 이를 바탕으로 이차원 배열을 사용한 dp로 구현했다. 가장 먼저 팰린드롬인지 여부를 나타내는 2차월 배열 p를 init해준다. N의 최댓값이 2,000인데 비해 질문의 ..
분류 전체보기
https://www.acmicpc.net/problem/17472 [17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net](https://www.acmicpc.net/problem/17472) 섬 구분하기 일단은 각 섬을 구분하기 위해 init_land 함수를 구현했다. 섬을 구분하도록 하는 변수 group을 2로 두고, BFS로 근처 땅을 모두 group으로 초기화하도록 했다. 섬 하나에 속한 땅을 모두 group으로 바꾼 후에는 1 증가하고 다음 땅을 찾는다. 즉, init_land 이후 ..
https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net R연산과 C연산 R연산과 C연산 중 어떤 것을 진행해야 할지 선택하기 위해 while문 안에서 매번 R과 C를 비교하도록 했다. 매 연산마다 R과 C 값이 달라지는데, R연산을 할 때는 C 값이, C연산을 할 때에는 R값이 달라진다. 따라서 R연산을 시작할 때 C를 0으로 초기화하고 map을 채우면서 가장 긴 열을 C에 넣어주었다. 반대로 C연산을 할 때에는 R을 0으로 초기화하고 가..
https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net BFS "최소 거리"를 구해야 하기 때문에 BFS를 사용해야 한다. 처음에는 열쇠 조건을 배열로 만들려고 DFS로 구현했었는데 시간 초과가 나왔다. BFS로 바꾸니까 통과할 수 있었다. 방문 체크 처음에 DFS를 사용했던 게 방문 체크에 조건이 복잡했기 때문이다. 만일 단순히 v[N][M]으로 체크를 해준다면, 막다른 길에 열쇠가 있을 때 열쇠를 갖고도 다시 못 돌아..
https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net BFS (2056ms) 각 간선을 List로 저장하고 Query가 주어질 때마다 간선 리스트를 바탕으로 BFS로 갈 수 있는 노드를 찾도록 했다. 단순한 방법으로 통과하기는 했지만 시간이 2056ms나 나왔다. N개의 노드에 N - 1개의 간선이 있고, 모든 노드가 이어져 있다는 조건으로, 사이클이 없는 트리 구조라는 것을 활용해보고 싶었지만 떠..
https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net BFS 어떤 편의점을 방문해야할지 모르기 때문에 BFS를 사용했다. 가장 먼저 떠올린 것은 가까이 있는 순서대로 방문하는 것이었으나, 가장 가까이 있는 편의점이 오히려 공연장과 멀어지거나, 혹은 다른 편의점들과 거리가 멀어 다음 편의점에 도달하지 못하는 경우가 있을 수 있다. 따라서 현재 위치에서 방문할 수 있는 경우를 Queue에 담아두고, 그곳에서 다시 방문할 수 있는 곳을 찾는 게 합리..
https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 물과 고슴도치의 순서 문제 조건 중에 이해하기 어려웠던 부분이 있었다. 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다. 이 부분인데, 물이 차오름과 동시에 고슴도치가 이동하니, 그 다음턴까지 파악을 해야 하나 하는 생각이 들었었다. 하지만 결국 정답은 물을 먼저 채우고, 그 다음 고슴도..
https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 나머지의 누적 합 이 문제에서 사용하는 건 나머지 값밖에 없기 때문에, 누적 합을 구하되 나머지 값만 누적하면 된다는 생각이 가장 먼저 들었다. 예제1과 같은 경우는 다음과 같이 진행되는 것이다. // 예제 1 5 3 1 2 3 1 2 numbers : [1 2 3 1 2] 누적 합 : [1 3 6 7 9] 나머지의 누적 합 : [1 0 0 1 0]..
