알고리즘/백준

백준 2661 - 좋은수열(Java)

2024. 5. 12. 15:13

https://www.acmicpc.net/problem/2661

문제

숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.

다음은 나쁜 수열의 예이다.

  • 33
  • 32121323
  • 123123213

다음은 좋은 수열의 예이다.

  • 2
  • 32
  • 32123
  • 1232123

길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열은 1213121이다.

입력

입력은 숫자 N하나로 이루어진다. N은 1 이상 80 이하이다.

출력

첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.

예제 입력 1 복사

7

예제 출력 1 복사

1213121

 

풀이

일단 빈 문자열을 선언 후,

백트래킹을 돌면서 1부터 3까지 추가해본다.

그렇게 만들어진 문자열을 check() 메서드에 던져서 가능한지 불가능한지를 확인한다.

문자열의 길이로 나누고 앞부분, 뒷부분을 비교해서 같은지를 보는 것.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ_2661_좋은수열 {
    static int N;
    static boolean exit = false;
    static String answer = "";
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        back(0);

    }
    public static void back(int cnt)
    {
        if(exit) return;
        if(cnt==N){
            System.out.println(answer);
            exit = true;
            return;
        }
        for(int i=1; i<4; i++)
        {
            answer+=i;
                if(check(answer))
                {
                    back(cnt+1);
                }
            answer = answer.substring(0,answer.length()-1);
        }

    }

    public static boolean check(String str) {
        for(int i = 1; i <= str.length() / 2; i++) {
            String front = str.substring(str.length() -i * 2, str.length() - i);
            String back = str.substring(str.length() - i, str.length());
            if(front.equals(back)) return false;
        }
        return true;
    }
}
저작자표시 비영리 변경금지 (새창열림)

'알고리즘 > 백준' 카테고리의 다른 글

백준 10026 - 적록색약 (Java)  (1) 2024.05.14
백준 6593 - 상범 빌딩 (Java)  (0) 2024.05.13
백준 10942 - 팰린드롬 ? (Java)  (0) 2024.05.09
백준 15989 - 1,2,3더하기 4 (Java)  (0) 2024.05.08
백준 11066 - 파일 합치기 (Java)  (0) 2024.05.07
'알고리즘/백준' 카테고리의 다른 글
  • 백준 10026 - 적록색약 (Java)
  • 백준 6593 - 상범 빌딩 (Java)
  • 백준 10942 - 팰린드롬 ? (Java)
  • 백준 15989 - 1,2,3더하기 4 (Java)
D_Helloper
D_Helloper
안녕_개발
D_Helloper
Hello_Develop
D_Helloper
전체
오늘
어제
  • 분류 전체보기 (116)
    • CS (23)
      • 네트워크 (16)
      • 운영체제 (6)
    • 알고리즘 (48)
      • 백준 (39)
      • 프로그래머스 (7)
      • SWEA (1)
    • DB (6)
      • SQLD (2)
      • DataBase (4)
    • JAVA (13)
    • ETC (16)
    • 일상 (5)
    • Develop (4)
      • Docker (1)
      • TIL (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • Contact

인기 글

태그

  • OSI 7계층
  • http method
  • TCP/IP 5계층
  • HTTP
  • restful
  • HTTP 상태코드
  • OSI 계층
  • REST
  • Internet 5계층
  • 네트워크 계층
  • HTTP 메소드
  • CRUD
  • REST API

최근 댓글

최근 글

hELLO · Designed By 정상우.
D_Helloper
백준 2661 - 좋은수열(Java)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.