da9dac

사실 달성했는지는 좀 됫는데 까먹고 글을 안올렸다...

시즌이 5월말 종료니 그때까지 플래를 찍고 싶은데

올려야 하는 점수가 200점...

당분간 알고리즘만 집중해서 풀면 가능은 할거 같은데

백수는 백준 티어보단 취직이 우선이니

취업만 하고 혼내줘야겠다 혼나는건 나일거 같지만...

문제

접근 방식

DP로 풀 필요도 없이 규칙만 찾으면 연산 한 줄로도 풀 수 있는 문제지만 그냥 DP로 풀어봤다.

우선 DP 테이블은 불리언 타입의 1차원 배열로 생성한 후에

상근이가 이기는 경우를 true, 창영이가 이기는 경우를 false로 채워주면 된다.

자기 순서에 1, 3, 4개 중 한 번씩 가져갈 수 있으니 이 경우에 상근이는 무조건 이길 수 있고

1, 3, 4번의 초기값은 true로 설정해준다.

9까지 직접 계산해 가며 표를 만들어보면 알 수 있는데

n번째 수를 가져가는 경우 중 상근이가 한 번이라도 가져가는 경우가 있다면

무조건 상근이가 이기는 경우이기 때문에

상근이가 처음에 1개를 가져가거나 3개를 가져가거나 4개를 가져간 후에

창근이가 지는 경우가 한 번이라도 있다면 상근이가 이기는 것이 된다.

dp[i] = (!dp[i - 1 || !dp[i - 3] || !dp[i - 4])

즉, 위와 같은 풀이가 나오게 된다.

이 문제는 n의 범위가 1,000 이하이기 때문에 dp 테이블이 설정이 가능하지만

같은 문제에 n의 범위만 int 형을 벗어난 돌 게임 6 문제 같은 경우에는

배열을 선언할 수 없기 때문에 다른 방법으로 풀어야 한다.

처음에 언급했던 것처럼 이 문제는 더 간단하게 풀 수 있는데

n을 7로 나눈 나머지가 0이거나 2인 경우에만 상근이가 지기 때문에

한 줄 만으로도 풀 수 있는 문제다.

풀이

class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        
        boolean[] dp = new boolean[1001];
        
        dp[1] = dp[3] = dp[4] = true;
        
        for (int i = 5; i <= n; i++) {
            dp[i] = (!dp[i - 1] || !dp[i - 3] || !dp[i - 4]);
        }
        
        System.out.println(dp[n] ? "SK" : "CY");
    }
}

문제

접근 방식

풀고 나서도 이게 그래프인지 DP 풀이인지 모르겠는 문제였다.

우선 그래프의 한 정점을 기준으로 위와 같이 이동할 수 있으며

2차원 배열을 처음부터 끝까지 돌면서 위와 같이 이동만 해주며 DP 테이블을 채워주면 된다.

따로 방문여부를 기록하지 않고 DP 테이블의 값이 0인지 아닌지로

확인하려 했는데 정점의 값이 음수인 경우도 있어서 합이 0일 때가 있을 수 있기 때문에

따로 방문 여부를 기록할 불리언 배열을 사용했다.

각 정점(i, j)에서 갈 수 있는 정점들을 방문하며

처음 방문한 정점(x, y)이면 방문 여부를 참으로 바꾸고,

(x, y)의 DP 테이블에 (i, j) 테이블의 값 + 현재 정점의 값을 기록하고

이미 방문한 정점이라면 이미 기록된 값과 새로운 값 중 더 작은 값을 기록한다.

목적지까지 테이블을 다 채운 후에 목적지의 값을 출력해주면 된다.

풀이

public class Main {

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

		int[] dx = {0, 1, 1, 1};
		int[] dy = {1, -1, 0, 1};
		int tc = 1;

		while (true) {
			int n = Integer.parseInt(br.readLine());

			if (n == 0) break;

			int[][] arr = new int[n][3];
			int[][] dp = new int[n][3];
			boolean[][] isVisited = new boolean[n][3];

			for (int i = 0; i < n; i++) {
				st = new StringTokenizer(br.readLine());

				for (int j = 0; j < 3; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			dp[0][1] = arr[0][1];
			isVisited[0][1] = true;

			for (int i = 0; i < n; i++) {
				for (int j = 0; j < 3; j++) {
					if (i == 0 && j == 0) continue;
					if (i == n - 1 && j == 1) {
						sb.append(tc++).append(". ").append(dp[i][j]).append("\n");
						break;
					}

					for (int dir = 0; dir < 4; dir++) {
						int x = i + dx[dir];
						int y = j + dy[dir];

						if (y < 0 || x >= n || y >= 3) continue;

						if (isVisited[x][y]) {
							dp[x][y] = Math.min(dp[x][y], dp[i][j] + arr[x][y]);
						} else {
							isVisited[x][y] = true;
							dp[x][y] = dp[i][j] + arr[x][y];
						}
					}
				}
			}
		}

		System.out.println(sb);
	}
}

문제

접근 방식

1원, 2원, 5원 총 3가지의 동전으로 1원부터 10원을 만드는 경우를 적어보면 다음과 같다.

1	1
2	11 2
3	111 12
4	1111 112 22
5	11111 1112 122 5
6	111111 11112 1122 15 222
7	1111111 111112 11122 115 1222 25
8	11111111 1111112 111122 1115 11222 125 2222
9	111111111 11111112 1111122 11115 111222 1125 12222 225
10	1111111111 111111112 11111122 111115 1111222 11125 112222 1225 22222 55

다시 1원만 사용한 경우, 1원과 2원을 사용한 경우, 세 가지 동전을 모두 사용한 경우로

경우의 수가 몇 개인지 정리해보면 다음과 같다. (0번 인덱스는 1이다.)

1원 동전으로는 값만큼 동전을 사용하면 모든 값을 만들 수 있기 때문에 모두 한 가지일 것이니 넘어가고

2원까지 추가로 사용해 n원을 만드는 경우를 먼저 생각해보겠다.

2원을 사용해서 2원 미만의 값은 당연히 만들 수 없으니

미만의 값들은 이전의 값을 그대로 사용하고 넘어가면 되고

2원 이상부터는 2원 동전을 사용할 수 있으니 값이 달라질 것이다.

위의 표에서 1원과 2원을 사용해 2원을 만드는 경우를 살펴보면

(1원으로 2를 만드는 경우인 1) + (2원으로 2 - 2원을 만드는 경우인 1) = 2가 되고

10원을 만드는 경우를 살펴보면

(1원으로 10원을 만드는 경우인 1 + 2원으로 (10 - 2)원을 만드는 경우인 5 = 6이 된다

이제 5원 동전까지 사용하는 경우도 마찬가지로

5원 이상부터 테이블의 값을 변경해주면 되고

10원을 만드는 경우를 살펴보면

(1원과 2원으로 10원을 만드는 경우인 6) + (5원으로 10 - 5원을 만드는 경우인 4) = 10이 된다.

점화식으로 정리하면 다음과 같다. (i는 목표가치, j는 현재 동전의 가치)

dp[i] = dp[i] + dp[i-j]

이때 dp[0] = 1로 초기화 해주어야

동전의 가치가 K인 경우를 처리할 수 있고

동전의 가치 이상의 dp 테이블을 수정할 때 처음에 dp[0]을 호출할 일이 있기 때문에

이를 0인 초기값으로 냅둬두면 테이블의 값이 변하지 않는다.

풀이

public class Main {

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

		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		int[] dp = new int[k + 1];

		dp[0] = 0;

		for (int i = 0; i < n; i++) {
			int coin = Integer.parseInt(br.readLine());

			for (int j = coin; j <= k; j++) {
				dp[j] += dp[j - coin];
			}
		}

		System.out.println(dp[k]);
	}
}

문제

접근 방식

카드를 n개 살 때, 가장 돈을 많이 쓰는 경우를 구해야 한다.

i번째 카드팩에는 카드가 i개 들어있다 했으니

만약 카드를 4개 사야한다 가정하면

1번팩 + 1번팩 + 1번팩 + 1번팩
1번팩 + 1번팩 + 2번팩
1번팩 + 3번팩
2번팩 + 2번팩
4번팩

위와 같은 경우의 수가 만들어진다.

4개가 아닌 3개로 줄여보면 다음과 같을 것이고

1번팩 + 1번팩 + 1번팩
1번팩 + 2번팩
3번팩

2개로 줄이면 다음과 같다.

1번팩 + 1번팩
2번팩

1개면 당연히 1번팩 하나만 살 수 있다.

결국 n개를 고를 때 i번 팩을 골랐다면 n-i개를 고를 수 있고

(i번 팩값 + n-i개를 고를 수 있는 경우 가장 큰 값) 이 된다.

이를 dp[i]를 채울 때마다 1번 팩을 고른 경우부터 i번 팩을 고른 경우까지 비교하면서

가장 큰 값을 채워주면 되고 하나를 고르고 두 개를 고르나 두 개를 고르고 하나를 고르나 같기 때문에

i번까지 비교할 필요도 없이 i/2번까지만 비교해줘도 괜찮다.

이를 점화식으로 표현하면 다음과 같다.

j = 1; j  <= i/2; j++
dp[i] = (max(dp[i], dp[j] + dp[i-j]))

확실히 DP 문제를 많이 풀다 보니 경우의 수를 적다보면 규칙이 보이게 되는거 같다

PS는 그냥 많이 풀어보는게 답...

풀이

public class Main {

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

        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.parseInt(st.nextToken());
            for (int j = 1; j <= i; j++) {
            	dp[i] = Math.max(dp[i], dp[j] + dp[i - j]);
            }
        }

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

문제

접근 방식

가장 많은 양의 포도주를 마실 수 있는 경우를 찾아야 하는데

두 번째 조건을 보면 연속으로 마실 수 있는 포도주는 두 잔까지고

이는 1,2번째 잔을 마셨다면 3번째 잔은 건너뛰고

4,5,6,...n번째 포도주 중 하나를 먹어야 한다는 말이다.

거꾸로 생각해 보면 두 잔을 연속으로 마실 때는 이전 잔을 무조건 마셨다는 것이 되고

한 잔만 마셨을 때는 바로 이전 잔을 제외한 이전의 어떠한 잔들 중 하나 이상은 마신 것이 된다.

만약 n번째 잔을 마실 때, 해당 잔이 연속으로 두 번째 마시고 있는 잔이라면

(n번 잔의 양 + n-1번 잔을 첫 번째로 마신 경우의 최댓값) 이 해당 경우의 최댓값이 되고

해당 잔이 연속이 아닌 첫 번째로 마시고 있는 잔이라면

n-2 이하 번의 잔의 최댓값 + n번 잔의 양이 최댓값이 된다.

점화식을 정리하면 다음과 같다.

dp[n][한 잔을 연속으로 마신 경우] = dp[n-2][누적 최댓값] + n번 잔의 양
dp[n][두 잔을 연속으로 마신 경우] = dp[n-1][한 잔을 연속으로 마신 경우] + n번 잔의 양
dp[n][누적 최댓값] = max(dp[n-1][누적 최댓값], dp[n][한 잔을 연속으로 마신 경우], dp[n][두 잔을 연속으로 마신 경우])

풀이

public class Main {

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

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

        int[] cups = new int[n + 1];
        int[][] dp = new int[n + 1][3];

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

        dp[1][0] = cups[1];
        dp[1][2] = cups[1];

        for (int i = 2; i <= n; i++) {
            dp[i][0] = dp[i - 2][2] + cups[i];
            dp[i][1] = dp[i - 1][0] + cups[i];
            dp[i][2] = Math.max(dp[i - 1][2], Math.max(dp[i][0], dp[i][1]));
        }

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

URL

scheme://호스트/리소스의 위치
http://www.server.com/resource/abcd.gif

브라우저(클라이언트)가 필요로 하는 리소스를 찾을 수 있게 리소스의 위치를 가리키는 식별자로

이를 통해 HTTP 및 다른 프로토콜을 통해 접근할 수 있다.

URL 문법

스킴(HTTP, FTP, SMTP 등)에 따라 문법이 조금씩 달라지긴 하지만

대부분의 문법은 일반적으로 아래와 같이 9개의 컴포넌트로 나뉜다.

<스킴>://<사용자명>:<비밀번호>@<호스트>:<포트>/<경로>;<파라미터>?<질의>#<프래그먼트>

이 모두를 사용하는 URL은 거의 없고, 핵심 컴포넌트는 스킴, 호스트, 경로다.

스킴

스킴은 URL을 사용하는 애플리케이션에게 어떤 프로토콜을 사용해 리소스를 요청할지 알려준다.

주로 http, ftp, rtsp, smtp 같은 프로토콜이 있고 알파벳으로 시작해야 하며

대소문자를 구분하지 않고 URL의 다른 컴포넌트와 : 로 구분한다.

호스트와 포트

www.host.com:80

호스트는 리소스를 호스팅 하고 있는 장비와 리소스에 접근할 수 있는 장비를 나타내는 컴포넌트로

호스트를 통해 장비에 접근하고 포트를 통해 접근한 장비에서 실행 중인 서버에 접근할 수 있다.

사용자 이름과 비밀번호

ftp://name:password@ftp.abc.def/ghj

서버가 가지고 있는 데이터에 접근을 허용하기 위해 요구하는 컴포넌트로 주로 FTP에서 사용되며

사용자 이름과 비밀번호를 요구하지 않는다면 굳이 사용할 필요는 없다.

경로

리소스가 서버의 어떤 경로에 있는지 알려주는 컴포넌트로 계층적 파일 시스템 경로와 유사한 구조를 가지며

'/' 문자를 기준으로 경로 조각으로 나뉘고, 각 경로 조각은 파라미터 컴포넌트를 가질 수 있다.

파라미터

ftp://exam.ex/e;type:d
ftp://exam.ex/e;type:d/test;type:b

애플리케이션이 서버에 정확한 요청을 하기 위해 필요한 입력 파라미터를 받는 데 사용하는 컴포넌트로

이름/값 쌍의 리스트로 URL의 다른 컴포넌트와 ';' 문자로 구분한다

질의 문자열

http://www.server.com/data/check?id=1234&name=test

데이터베이스 같은 서비스들이 요청받을 리로스 형식의 범위를 효율적으로 좁히기 위해 사용하는 컴포넌트로

URL에서 물음표(?)와 물음표의 우측에 오는 질의 컴포넌트로 구성된다.

질의 컴포넌트는 이름=값 쌍 형태를 가지고 있고 각각의 질의 컴포넌트는 '&'로 구분한다.

프래그먼트

http://www.server.com/index.html#test

리소스의 특정 부분을 가리킬 수 있는 컴포넌트로 용량이 큰 텍스트의 특정 절을 가리키거나

HTML 문서의 특정 이미지나 일부분을 가리킬 수 있고 URL의 오른쪽에 # 문자에 이어서 온다.

일반적으로 HTTP 서버는 일부가 아닌 전체를 다루기 때문에 클라이언트가 서버에 프래그먼트를 전달하는 것이 아닌

클라이언트가 서버에게 전체 리소소를 받아 프래그먼트를 사용해 일부분을 보여준다.

단축 URL

리소스 안에 있는 리소스를 간결하게 기술하는 데 사용할 수 있는 방식의 URL

상대 URL

기저 URL : http://www.server.com/index.html
상대 URL : ./test.html
사용 예시 : <a href = "./test.html">
새로운 절대 URL :http://www.server.com/test.html

이전까지 살펴본 URL은 절대 URL로 리소스에 접근하기 위해 필요한 모든 정보를 갖고 있다면

상대 URL은 모든 정보를 담고 있지 않기 때문에 기저(base)라는 다른 URL을 사용해 필요한 정보를 얻어야 한다.

상대 URL만으로는 리소스에 접근할 수 있는 온전한 URL을 알 수 없지만

기저 URL에 스킴과 호스트 등의 컴포넌트가 모두 포함되어 있어 이를 참고해 온전한 URL을 얻을 수 있다.

위와 같은 과정으로 기저 URL을 얻어 절대 URL이 만들어진다.

URL 확장

브라우저가 사용자가 URL을 빠르게 입력할 수 있게 지원하는 자동완성 기능이다.

naver를 입력하면 호스트명에 자동으로 'www.'과 '.com'을 붙여서 'www.naver.com'을 만들어주는

단순한 휴리스틱만 사용하는 호스트 명 확장 방식과

과거에 사용자가 방문했던 URL 기록을 저장해 두고 이를 사용해 입력에 따른 선택 목록을 보여주는

히스토리 확장 방식이 있다.

미래

URL은 주소이지 실제 이름이 아니기 때문에 리소스가 특정 시점에 어떤 곳에 위치하고 있다는 것을 알려줄 뿐이라

리소스가 옮겨지면 더 이상 사용할 수 없는 URL이 되어버리고 기존 URL이 가리키고 있던 객체를 찾을 수 없다.

이런 문제를 예방하기 위해서는 객체의 위치와 상관없이 그 객체를 가리키는 고유한 실제 이름을 사용하는 것으로

그러한 방법이 바로 이전에 간단하게 살펴봤던 URN이다. (PURL)

하지만 주소 체계를 바꾸는 표준화 작업은 매우 큰 작업이기 때문에 많은 시간이 필요하고

이러한 작업이 긴급하진 않기 때문에 앞으로 당분간은 URL이 계속 사용될 것이다.

문제

접근 방식

한 자리의 경우 : 1
두 자리의 경우 : 11, 00
세 자리의 경우 : 111, 100, 001
네 자리의 경우 : 1111, 1100, 1001, 0011, 0000
다섯 자리의 경우 : 11111, 11100, 11001, 10011, 10000, 00111, 00100, 00001

각 자릿수 별로 경우의 수를 적어보면 위와 같다.

우리가 사용할 수 있는 숫자는 한 자리인 1과 두 자리인 00 두 가지만 있는데

만약 여섯 자리의 수를 만들어야 한다 가정하면

첫자리에 1이 오면 그 뒤에는 다섯 자리의 수가 올 수 있을 테니

기존에 구해둔 다섯 자리의 경우만큼 만들 수 있을 것이고

첫자리에 00이 오면 그 뒤에는 네 자리의 수가 올 수 있으니

기존에 구해둔 네 자리의 경우만큼 만들 수 있을 것이다.

결국 1로 시작하는 경우와 00으로 시작하는 경우를 합쳐주면

n자리의 수를 만들 수 있는 경우의 수를 구할 수 있다.

점화식을 정리하면

첫자리에 1이 오는 경우는 (n-1)자리의 경우의 수가 되고

첫 자리에 00이 오는 경우는 (n-2)자리의 경우의 수가 되니

f(n) = f(n-1) + f(n-2) 가 된다.

풀이

public class Main {

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

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

        int[] arr = new int[1000001];

        arr[1] = 1;
        arr[2] = 2;

        for (int i = 3; i <= n; i++) arr[i] = (arr[i - 1] + arr[i - 2]) % 15746;

        System.out.println(arr[n]);
    }
}