3085번: 사탕 게임
예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.
www.acmicpc.net
👨💻 문제
상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.
가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)
다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.
사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.
출력
첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.
예제 입력 1
3
CCP
CCP
PPC
예제 출력 1
3
예제 입력 2
4
PPPP
CYZY
CCPY
PPCC
예제 출력 2
4
예제 입력 3
5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ
예제 출력 3
4
힌트
예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.
정답 코드
답안 1
답안 2
답안 3
문제 풀이
주어진 n *n 크기의 배열에 있는 요소를 하나하나 확인하면서 풀어야 하는 문제이다. 이러한 문제는 2중 for문으로 요소를 탐색한다. 탐색하는 요소의 오른쪽 혹은 밑에 있는 요소와 탐색 중인 요소의 위치를 바꾼 뒤 count 함수로 진입한다. count 함수 내에서는 다시 n * n 배열을 하나하나 탐색하며 각 행과 열에 연속된 요소가 몇 개인지 확인한다. count 함수 실행을 마치고 나면 바꿨던 요소를 다시 원상복귀시키고 다음 요소를 탐색한다. 이 같은 작업을 모든 요소를 확인할 때까지 반복 수행한다.
함께 보기
[Python/파이썬] 백준 알고리즘 3085 - 사탕 게임 (Brute Force)
""" 1. 아이디어 브루트포스로 다 돌려본다. N이 최대 50이므로 가능하다. 한 위치에서 상하좌우와 바꿀 수 있지만 겹치므로 아래와 오른쪽만 계속해서 바꿔주면 된다. 바꿔준 뒤, 전체 보드에서
kbwplace.tistory.com
백준 3085번 파이썬 문제풀이(브루트 포스 - 사탕 게임)
코드 n = int(input()) array = [] for _ in range(n): colors = list(map(str, input())) array.append(colors) maxCount = 0 #최대 사탕 개수를 초기화 # 배열의 행 마다 같은 색의 사탕이 몇개 있는지 계산 def width(): global maxCount
ji-gwang.tistory.com
백준3085(파이썬) - 사탕 게임
https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 먼저 이문제는 탐색 문제이다. 좌우 또는 상하로 한번 자리를 옮긴 후
resilient-923.tistory.com
[백준 3085번] 사탕 게임 - 파이썬
① 문제 링크 https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net ② 알고리즘 분류 구현, 브루트포스 알고리즘 ③ ★문제
data-flower.tistory.com
'👩💻 Programming > Coding Test 문제 풀이' 카테고리의 다른 글
| [Baekjoon] 14500 테트로미노(자바스크립트/NodeJs) (1) | 2023.01.16 |
|---|---|
| [Baekjoon] 1107 리모컨(자바스크립트/NodeJs) (0) | 2023.01.15 |
| [Baekjoon] 2309 일곱 난쟁이(자바스크립트/NodeJs) (0) | 2023.01.15 |
| [이코테] 그리디_1이 될 때까지(자바스크립트) (0) | 2023.01.13 |
| [이코테] 그리디_숫자 카드 게임(자바스크립트) (0) | 2023.01.12 |
댓글