쏚쏚스포이드

백준 포도주 시식

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

접근 방식

조건 : 연속으로 놓여 있는 3잔을 모두 마실 수는 없음

최초에 값을 초기화할 때 앞의 2개의 잔을 모두 마실 필요가 있나? x

마셨을 때 : 1

마시지 않았을 때 0

기준으로 표현하자면,

경우의 수는 110, 101, 011로 좁혀지고, 010은 고려대상이 아님

구현 방법

• DP배열에서 위 접근방식을 적용하면 해결됨

⇒

• 바텀업으로 값을 채워나감
• 최초 값은 index 2까지 초기화
  • 0 : 1
  • 1 : 11
  • 2 : 101, 110, 011
• 이후 점화식을 코드로 구현
  • i index 기준으로 봤을 때 각 경우의 수는 아래와 같이 표현됨
  • 110 : dp[i-1]
  • 101 : dp[i-2] + arr[i]
  • 011 : dp[i-3] + arr[i-1] + arr[i]

풀이

import java.io.*;
import java.util.*;

public class p2156 {
    static int[] arr;
    static int[] dp;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        arr = new int[n];
        dp = new int[n];

        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        if(n == 1){
            System.out.println(arr[0]);
            return;
        }

        if(n == 2){
            System.out.println(arr[0] + arr[1]);
            return;
        }

        dp[0] = arr[0];
        dp[1] = arr[0] + arr[1];
        dp[2] = Integer.max(dp[1],
                Integer.max(dp[0] + arr[2], // 101
                        arr[1] + arr[2])); // 011

        for(int i = 3; i < n; i++){
            dp[i] = Integer.max(dp[i-1], // 110
                    Integer.max(dp[i-2] + arr[i], // 101
                            dp[i-3] + arr[i-1] + arr[i])); // 011
        }

        System.out.println(dp[n-1]);
    }
}

후기

점화식을 세워서 진행하는 바텀업 DP 문제는 경우의 수를 어떻게 잘 구현 해야할지 머릿속에서 잘 구상해야하는데 이게 아직도 어려운 것 같다.

워터마크(Watermark)란?

워터마크(Watermark)는 디지털 콘텐츠(이미지, 영상, 오디오, 문서 등)에 저작권 보호, 출처 표기, 위변조 방지 등의 목적으로 삽입되는 표식이다. 워터마크는 가시적(Visible)과 비가시적(Invisible) 방식으로 나뉜다.

1. 가시적 워터마크 (Visible Watermark)

• 정의

이미지, 영상, 문서 등에 눈에 보이는 형태로 삽입된 워터마크를 의미한다.

• 특징
  • 사람이 직접 볼 수 있음 (예: 로고, 텍스트, 투명한 마크)
  • 저작권 보호 및 출처 표시 목적
  • 복제 방지를 위한 억제 효과
  • 그러나 이미지 편집 기술(포토샵 등)로 제거 가능
• 예시
  • 사진에 삽입된 "© 2025 PhotographerName" 표시
  • 영상의 한쪽 구석에 있는 방송국 로고 (예: "KBS", "MBC")
  • PDF 문서의 배경에 투명하게 삽입된 회사명

2. 비가시적 워터마크 (Invisible Watermark)

• 정의

사람의 눈에는 보이지 않지만, 디지털 신호(이미지, 영상, 오디오, 문서)에 숨겨진 형태로 삽입된 워터마크를 의미한다.

• 특징
  • 사람이 직접 볼 수 없음 (특정 소프트웨어나 알고리즘을 통해 확인 가능)
  • 저작권 보호 및 원본 출처 확인
  • 변형, 편집 후에도 검출 가능 (강인성에 따라 다름)
  • 이미지, 오디오, 영상에 널리 사용됨
• 기술적 기법
  • 공간 영역 기법: 픽셀값에 미세한 변화 삽입
  • 주파수 영역 기법: 푸리에 변환(DFT), 웨이브렛 변환(DWT) 등을 활용해 삽입
  • 양자화 지수 변조(QIM): 특정 패턴을 신호에 삽입하여 탐지
• 예시
  • 사진 속 특정 픽셀에 디지털 서명 숨기기
  • 영화나 음악 파일에 저작권 정보 삽입
  • 문서에 특정한 패턴을 추가해 출처 확인

3. 가시적 vs 비가시적 워터마크 비교

결론

• 가시적 워터마크는 저작권 보호를 강조하고 쉽게 알아볼 수 있는 장점이 있지만 제거될 가능성이 있다.
• 비가시적 워터마크는 콘텐츠의 무결성을 유지하면서도 추적이 가능하지만, 분석 도구가 필요하다.
• 두 가지 방법을 함께 사용하면 보안성과 저작권 보호 효과를 극대화할 수 있다.

백준 감소하는 수(줄어드는 수)

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

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

접근 방식

최초엔 n까지 범위의 수를 생각했는데, 잘못 생각한 것이였고, 앞자리부터 점점 감소하는 수의 모든 경우의 수 중 몇번째인지 n으로 입력받아 찾는 문제

구현 방법

• 감소하는 수에 대해 모든 조합을 찾은 후 정렬해 수행
• 이 때 최대 수의 범위까지 1씩 더해가며 찾는 것이 아닌, 값이 들어갈 수 있는 범위에 대해서만 찾기

⇒

• 9876543210 까지가 최대 수
• 재귀에서 자릿수(depth)를 받아서 depth 범위만큼 foreach돈다.
• 기본적으로 for문 돌 때 자기보다 낮은 수에 대해서만 수행
• 재귀 안에서 count가 같으면 return - count는 static으로 갖고있기에 종료가능
• for문이 다 돌면 재귀호출 시행

풀이

package Baekjoon.gold;

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

public class p1174 {

    static Stack<Long> st = new Stack<>();
    static ArrayList<Long> al = new ArrayList<>();

    static int count = 0;
    static int n;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        /*
         0, 1, 2, 3, 4, 5, 6, 7, 8, 9
         10 | 20, 21 | 30, 31, 32 | 40, 41, 42, 43 | 50, 51, 52, 53, 54 |
         60, 61, 62, 63, 64, 65 | 70, 71, 72, 73, 74, 75, 76 |
         80, 81, 82, 83, 84, 85, 86, 87 | 90, 91, 92, 93, 94, 95, 96, 97, 98 |
         210 |320, 321, 310 | 410, 420, 421, 430, 431, 432
         */

        //9 -> 8 7 6 5 4 3 2 1 0
        //8 -> 7 6 5 4 3 2 1 0
        //7 -> 6 5 4 3 2 1 0
        //6 -> 5 4 3 2 1 0
        //5 -> 4 3 2 1 0
        //4 -> 3 2 1 0
        //3 -> 2 1 0
        //2 -> 1 0
        //1 -> 0

        // 10 20 21 30 31 32
        //9876543210 까지가 최대 수
        //재귀에서 자릿수(depth)를 받아서 depth 범위만큼 foreach돈다.
        //기본적으로 for문 돌 때 자기보다 낮은 수에 대해서만 수행
        //재귀 안에서 count가 같으면 return - count는 static으로 갖고있기에 종료가능
        //for문이 다 돌면 재귀호출 시행

        if(n <= 10){
            System.out.println(n-1);
            return;
        }
        recur(10);
        List<Long> list = al.stream().sorted().collect(Collectors.toList());

        long result = -1;
        if(list.size() >= n){
            result = list.get(n-1);
        }

        System.out.println(result);
    }

    private static void recur(long nowNum){
        for(long i = 0; i < nowNum; i++){
            count++;
            st.push(i);
            st.forEach(sb::append);
            al.add(Long.valueOf(sb.toString()));
            sb.setLength(0);
            recur(i);
            st.pop();
        }
    }
}

후기

최초에 문제를 잘못 읽었고, 이후엔 전체 탐색을 효율적으로 하기위한 노력(가지치기)을 하는 데 시간을 많이 썼음