https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 우선 이 문제는 RGB거리1의 확장판이다. 직전에 고른 색만 고를 수 없는 것이 아니라, 1번째 집과 N번째 집의 색도 달라야 하므로 원형문제라고 볼 수 있다! 우선, RGB색으로 칠하는 비용을 2차원 배열에 모조리 저장한다. for문을 3번 돌려서 1번 집이 R, G, B 색을 차례로 하나씩 선택하는 경우의 최솟값을 계산한다. 1번 집이 만약 Red를 골랐다면, ..
https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 기본적인 bfs문제에 약간의 테크닉을 요구하는 문제이다. 우선 C가 두개 주어지므로 그냥 먼저 나오는 C를 시작점이라고 치고, 늦게 나오는 C를 도착점이라 친다. 그리고 시작점을 큐에 넣고 bfs를 시작하는데, 큐의 맨 앞에 것을 가져와서 4가지 방향을 탐색하는 건 기존 bfs와 동일하다. 그러나 여기서 레이저의 특징을 이용해야한다! 레이저는 한 방향으로만 직진하므로, while문을 통해..
https://www.acmicpc.net/problem/19948 19948번: 음유시인 영재 감수성이 뛰어난 음유시인 영재는 일상생활 중에 번뜩 시상이 떠오르곤 한다. 하지만 기억력이 좋지 못한 영재는 시상이 떠오르면 그 순간 컴퓨터로 기록해야만 안 까먹는다! 시는 대문자, 소 www.acmicpc.net 이 문제.. 약 10번의 시도 끝에 겨우 풀었다. C++를 이용한 답안 코드가 없길래 혹시 누군가 필요할까 싶어 글을 적게 되었다. 우선 문제를 꼼꼼히 읽자..! 자신과 똑같은 것이 다음에 오면 2번이 아니라 1번으로 친다는 것을 읽지못하고 좀 오래 헤매었다. 그리고, 주어진 키보드로 제목까지 입력할 수 있어야한다. 문제 풀이 우선 입력들을 다 받자 제목이 되는 문자들을 다 저장한다. 원하..
https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 문제분석 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력..
https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 문제풀이 dfs문제이다. 알맞은 조합을 고르는 법은 다음과 같다. 1 2 3 3 1 2 위 테이블에서 처음 인덱스 1 -> arr[1]은 3 -> 인덱스 3 -> arr[3]은 2 -> 인덱스 2 -> arr[2]는 1 순서로 탐색을 진행한다. 만약 이 때, 처음 인덱스로 돌아온다면 조건을 만족시키도록 수를 뽑을 수 있는 경우인 것이다! 이 경우에는 pivot만을 저장해주고, i를 1..
https://www.acmicpc.net/problem/16955 16955번: 오목, 이길 수 있을까? 구사과와 큐브러버는 10×10 크기의 바둑판에서 오목을 하고 있다. 턴은 구사과가 먼저 갖는다. 바둑판의 상태가 주어진다. 구사과가 턴을 한 번 더 가졌을 때, 이길 수 있는지 구하는 프로그램을 www.acmicpc.net 문제분석 누구나 쉽게 알 수 있는 오목게임이다. 구사과와 큐브러버는 10x10크기의 바둑판에서 오목을 하고 있다. 턴은 구사과가 먼저 갖는데, 바둑판의 상태가 입력으로 주어지고 구사과가 턴을 한 번 더 가졌을 때, 즉, 한 수를 두었을 때 이길 수 있는지 구하는 프로그램을 작성해아한다. 오목의 승리 룰은 가로,세로 대각선 방향 중 하나에서 자신의 돌이 5개 이상 연속하는 것이다...
