어흥

문제 링크: https://www.acmicpc.net/problem/7348 7348번: 테이블 옮기기 문제 ACM 회사는 아래 그림과 같은 빌딩의 한 층을 빌렸다. 이 층의 방들은 다음과 같이 번호가 매겨져 있다. 그림처럼 이 층에는 복도를 따라 양쪽 사이드로 각각 200개의 방이 있다. ACM 회사는 이 방들을 리모델링하려는 계획을 세웠다. 당연히 어떤 방에서 다른 방으로 많은 테이블을 옮겨야 한다. 이때 복도는 좁고 테이블이 커서 단지 하나의 테이블만 이 복도를 지날 수 있다. 방에서 다른 방으로 테이블을 옮기는 데 소요되는 시간은 10분 이다. i www.acmicpc.net 1. 주의할 점 - 처음에 입력받는 숫자가 두번째 숫자보다 클 수도 있다 - 서로 마주보는 숫자는 공통된 통로를 지닌다 ..

[팰린드롬] 문제 링크: https://www.acmicpc.net/problem/2079 2079번: 팰린드롬 문제 팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 'aba'나 'a'와 같은 단어는 팰린드롬이며, 'abaccbcb'나 'anavolimilana'와 같은 단어는 팰린드롬이 아니다. 만일 어떤 단어가 팰린드롬이 아니라면, 그 단어는 여러 개의 팰린드롬으로 나누어질 수 있을 것이다. 단어가 주어졌을 때 이를 여러 개의 팰린드롬으로 나누되, 나누어진 팰린드롬의 개수가 최소가 되도록 나누려고 한다. 예를 들어 ab www.acmicpc.net [팰린드롬 분할]문제 링크: https://www.acmicpc.net/problem/1509 1509번: 팰린..

문제 링크: https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 매겨져 있다고 생각한다) 먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되 www.acmicpc.net 1. 주의할 점 - 모든 Node에 대해 돌릴 경우 N^2 -> 시간초과 발생 - 시작 Node를 기준으로 Leaf 까지..

문제 링크: https://www.acmicpc.net/problem/14405 14405번: 피카츄 피카츄는 "pi", "ka", "chu"를 발음할 수 있다. 따라서, 피카츄는 이 세 음절을 합친 단어만 발음할 수 있다. 예를 들면, "pikapi"와 "pikachu"가 있다. 문자열 S가 주어졌을 때, 피카츄가 발음할 수 있는 문자열인지 아닌지 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 주의할 점 - 3가지 단어 말고 다른 문자로 시작해도 NO 출력시켜야한다. 2. 구현 - Idx=0을 기준으로 입력받은 String에서 Idx번째 문자가 셋중 하나와 같으면 나머지 또한 같은지 비교한다. - 셋과 모두 다르다면 While문을 빠져오도록 설계한다. #include #include ..

문제 링크: https://www.acmicpc.net/problem/2151 2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 이 곳을 통과한다. ‘!’은 거울을 설치할 수 있는 위치를 나타내고, ‘*’은 빛이 통과할 수 없는 벽을 나타낸다. www.acmicpc.net 1. 주의할 점 - BFS로 풀지만 어느 방향에서 왔는지 기억하지 않으면 답을 도출할 수 없다. - 시작점을 기준으로 반대지점까지 도착하도록 설계하면 된다 - 거울을 놓을 수 있지만 놓지 않는 경우도 처리해야한다. 2. 구현 - 한 방향에서 시작해서 끝까지 ..

문제 링크: https://www.acmicpc.net/problem/9207 9207번: 페그 솔리테어 문제 페그 솔리테어는 구멍이 뚫려있는 이차원 게임판에서 하는 게임이다. 각 구멍에는 핀을 하나 꽂을 수 있다. 핀은 수평, 수직 방향으로 인접한 핀을 뛰어넘어서 그 핀의 다음 칸으로 이동하는 것만 허용된다. 인접한 핀의 다음 칸은 비어있어야 하고 그 인접한 핀은 제거된다. 현재 게임판에 꽂혀있는 핀의 상태가 주어진다. 이때, 핀을 적절히 움직여서 게임판에 남아있는 핀의 개수를 최소로 하려고 한다. 또, 그렇게 남기기 위해 필요한 최소 이동횟수를 구하는 프 www.acmicpc.net 1. 주의할 점 - 백트레킹을 통해서 구현한다(핀의 최대 개수: 8) - 맵을 바꾼 후, 다시 돌아왔을 때 맵을 복구하..

문제 링크: https://www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. N은 100보다 작거나 같으며, M도 100보다 작거나 같다. L은 100보다 크거나 같고, 1000보다 작거나 같다. 모든 휴게소의 위치는 중복되지 않으며, N+M은 L보다 작다. 둘째 줄에, 휴게소의 위치가 공백을 사이에 두고 주어진다. www.acmicpc.net 1. 주의할 점 - 시작지점과 끝지점(고속도로의 길이)도 포함해야한다. - 이분탐색으로 해결한다. 2. 구현 - 첫 번째 구현방법: 구간과 구간사이의 길이를 구해서 우선순위큐에 적재한다. 우선순위큐의 Top에 있는 원소를 뽑아서 반..

문제 링크: https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 1. 주의할 점 - DP문제다. 백트레킹으로 접근할 생각하지 말자 - DP문제라는건 알았지만 점화식을 세우는게 쉽지 않다. 문제를 해결하고 다른사람들의 점화식을 확인해본 결과 나와 같은 점화식은 찾지못했다(내가 너무 어렵게 해결한것 같다). 2. 구현 - 우선 나는 0,1로 이루어진 비트라고 생각하고 접근했다(문제와 달리 행:2 , 열:N이라고 가정) - DP[숫자의 길이(=N)][마지막에서 2번째 번호][마지막 번호] 의 형태로 배열을 세웠다. ex)[N][0][0] : N의 길이면서 마지지막이 00으로 끝나는 수,..