joseph0528 코딩 블로그

이 문제는 초기 문자열과 만들어야하는 문자열이 주어질 때, 각 위치의 스티커를 떼고 붙이고, 구매 등의 방법을 사용해 만들어야하는 문자열이 초기 문자열의 부분 문자열이 되도록 하는 최소값을 구하는 문제이다. 문제 설명만 봤을 때는 어려워 보일 수도 있지만 문자열의 길이가 500이 안되기 때문에 모든 경우를 탐색하면서 최소값을 계산해주면 된다. 부분 문자열을 만들 수 없는 경우 -1을 출력하라고 되어있는데, 이는 구매할 수 있는 스티커 중에 부분 문자열에 필요한 스티커가 없을 때 -1을 출력해주면 된다. 부분 문자열을 만들기 위해서 부분 문자열에 해당될 부분 중, 바꿔야 될 부분의 스티커를 모두 떼준다. 그후 뗀 스티커와 다른 범위에 있는 스티커까지 고려해서 어느걸 고르는 것이 최소값이 되는지 판단해주면 ..

문제를 요약하면 동그라미, 세모, 네모를 같은 모양이 연속으로 나열되도록 최소 횟수로 바꾸는 문제이다. 이문제에서 입력이 1,2,3 즉 동그라미, 세모, 네모만 존재하기 때문에 이 3개의 도형을 배치할 수 있는 경우의 수 6개를 반복문으로 탐색하면서 최소 개수를 구해주는 방식을 떠올릴 수 있다. 그다음은 어떻게 최소 개수를 구하냐 인데, 일단 두 도형을 바꿨을 때, 두 도형이 모두 최종적으로 있어야 하는 구간에 들어간다면 이 방법이 두 도형의 최소 변경 횟수가 될 것이다. 예를 들어보자. 1 3 3 2 1 1 3 2 라는 입력이 들어오고, 3 2 1 순서로 나타난다고 해보자. 그러면 최종적으로 3 3 3 2 2 1 1 1 을 만들어야 한다. 초기 입력을 숫자의 개수에 따른 구간을 나눠 보면 1 3 3 |..

문제를 간단하게 요약하면 처음부터 i를 증가하며 카운팅을 하는데 i번째 값이 i 라면 그 값을 지우고 카운팅을 1부터 다시 한다. 이렇게 계속 반복해서 값을 계속 지우는데 지워지는 값이 1부터 차례대로 지워지게 하는 크기가 K이 배열에서 n개의 인덱스가 주어지면 그 위치의 값을 출력하는 문제이다. K=5 일 때 [1, 3, 2, 5, 4] 이렇게 배열을 만들면 차례로 값을 지울 수 있다. 처음에는 i가 1이고 값도 1이므로 1을 지우고 3부터 다시 i=1을 시작해서 카운팅 해 나가면 2가 지워지고 계속 반복하게 되면 1, 2, 3, 4, 5 순서대로 지워지게 된다. 여기서 한가지 알 수 있는 사실은 i 번째 값이 지워졌다면 다음 값은 i+(i+1) = 2i+1 위치에 있어야 한다. 그러므로 1부터 K까지..

solved.ac 티어 : 골드 3 www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 태그는 bfs(너비 우선 탐색)이 붙어있긴하지만 bfs를 안쓰고 dfs와 몇번의 전체 탐색만 해주면 된다. 탐색해서 알아내야할 정보는 한 위치로부터 x축으로 가장 가까운 섬과의 거리,그 위치로부터 y축으로 가장 가까운 섬과의 거리, 섬의 번호, 한 위치로부터 가장 가까운 섬의 번호 이렇게 4개를 알아내면 된다. 입력 예시로 예를 들면 # # # 1 2 2 1 # # # # # # ..

solved.ac 난이도 : 플래 5 www.acmicpc.net/problem/2505 2505번: 두 번 뒤집기 첫줄에는 숫자판의 크기를 나타내는 정수 N (5≤N≤10,000)이 주어진다. 그 다음 줄에는 두 개의 구간이 뒤집혀진 놀이판의 상태를 나타내는 숫자들이 하나의 공백을 두고 나타난다. www.acmicpc.net 이 문제의 풀이는 의외로 간단하다. 이문제 조건에서 한 번만 뒤집는다고 바꿨을 때 어떻게 하면 구할 수 있을까? 한 번만 뒤집는 경우 해당 값이랑 해당 위치가 다를 경우 해당 위치랑 같은 값을 찾아서 반전을 시켜주면 된다. 이걸 두 번 뒤집기에 똑같이 적용해서 값이 다를 경우 찾아서 바꿔주면 된다. 하지만 이렇게 했을 경우 반례가 생긴다. 하나의 예를 들어보면 10 1 8 7 6 ..