2016년 4월 25일 월요일

11966 - 2의 제곱인가?

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

2의 제곱은 2로 한번만 나누어 떨어진다.

6362 - Unimodal Palindromic Decompositions

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

$N=7$일 때 아래와 같이 표현할 수 있다.
[그림 1]
가운데 숫자를 회색숫자(1,2,3..)만큼 쪼개서 양쪽에 붙인다고 생각했다. [그림 1]은 해석하면 [그림 2]와 같은 뜻이다.
[그림 2]
하지만 문제의 정의상 가운데에서 끝으로 갈수록 숫자가 (같거나) 작아야하므로 (3 1 3) 이나 (1 2 1 2 1) 같은 수열은 정답으로 셀 수 없다. 따라서 쪼개는 수(회색숫자)를 $k$라고 했을 때, $k \le n-2k$ 인 경우에만 쪼갤 수 있다. 
$k$는 쪼개서 옆에 붙인 숫자이다. 이 말은 가장 끝에 $k$ 보다 큰 수는 없다는 것이다. 항상 $k=1$ 가 아닌 $k=$이전의 $k_{prev}$ 부터 시작해야 한다.

짝수의 경우 역시 위와 동일하게 진행하되, (8) -> (4 4) 와 같은 경우가 가능하기 때문에 $k \le \frac{n}{2}$ 인지를 더해준다.

참고로 $N=8$ 일 때 (1 2 2 2 1) 에서 (1 2 1 1 2 1) 을 안 세도록 해야한다.

2016년 4월 24일 일요일

C++ Code Template

문제풀이를 위한 C++ 코드 템플릿
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <functional>
#include <limits>
#include <complex>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>
using namespaces std;

#define INF 987654321

typedef long long lld;
typedef pair<int, int> ii;

int main(){
   
    return 0;
}

채점 서버의 사용 컴파일러가 GCC 4.8.0 이상 버전이라면 #include <bits/stdc++.h>로 대체 가능하다.

2016년 4월 23일 토요일

2848 - 고창어

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

그냥 쭉 쓰다보니 코드가 너무 길어졌다.
새로 정의한 사전순 문자열로부터 문자의 순서를 재정의한다.
예제 같은 경우는 l->u, l->k, u->k, k->a 이렇게 4개

1. 올바른 순서가 없는 경우
 : 모순이 존재한다는 것. 싸이클이 있다는 것이다.
 : 플로이드 돌린 후에 다시 자신으로 돌아오는 경로가 있으면 싸이클임.

2. 가능한 순서가 여러개인 경우
 : 사전의 첫 글자가 여러개이거나, (첫 글자로부터) k번째 숫자에 올 수 있는 수가 여러개인 경우.

위에 적은 것만 구현했는데 코드가 1.6KB나 된다. 소스 정말 더럽다.

2016년 4월 22일 금요일

11340 - Making the Grade?

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

$x$를 기말 점수, 나머지를 $a, b, c$라 하면 다음을 만족하는 $x$ $$ 40x \ge \frac{9000}{15a+20b+25c} $$
#include <bits/stdc++.h>
using namespace std;

int main(){
    int T;
    scanf("%d", &T);
    for(int i=0; i<T; ++i){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        int r = ceil((1800-3*a-4*b-5*c)/8.);
        if( r > 100 ) puts("impossible");
        else printf("%d\n", r);
    }
    return 0;
}

1727 - 커플 만들기

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

비교하고자 하는 배열 $a$의 크기는 항상 배열 $b$보다 작다.
배열 $a$로부터 차이를 최소로 하는 배열 $\{ b_i, b_{i+1}, \dots, b_j \}$ $(0 \le i \le j \le n)$ 을 찾는다.

스위핑으로 되려나싶어서 코드를 다음과 같이 작성해봤다.
int ptr = -1, sum = 0;
for(int i=0; i<n; ++i){
    int val = INF;
    for(int j=ptr+1; j<=m-(n-i); ++j){
        if(val > abs(a[i]-b[j])){
            val = abs(a[i]-b[j]);
            ptr = j;
        }
    }
    sum += val;
}
return sum;

그러나 아래와 같이 이전에 작은 손해가 있지만 결과적으로 최소가 나오는 케이스에서 오답을 출력했다.
3 6
10 20 30
9 10 11 100 101 102

A = [10, 20, 30]
B = [ 9, 10, 11]
이여야하는데, 원소가 하나씩 밀려서 B = [10, 11, 100] 가 되버린 것이다.

이거 DP구나 깨닫고 $O(|A||B|)$ 를 다 해보자 싶었다.
int solve(int apos, int bpos){
    if(apos == n) return 0;
    
    int& r = dp[apos][bpos];
    if(r != -1) return r;
    
    r = INF;
    for(int i=bpos; i<=m-(n-apos); ++i){
        r = min(r, abs(a[apos]-b[i]) + solve(apos+1, i+1));
    }
    return r;
}

범위를 $|B|$ 배열 길이만큼이 아닌, 남은 $|A|$의 길이만큼으로 했지만 역시 느렸다. 속도가 빠른 소스들을 보니 이렇게 해결한 것 같다.
$min( b[bpos]$를 선택하는 경우, 선택하지 않고 $b[bpos+1]$과 $a[pos]$를 매칭하는 경우 $)$

재귀가 2번씩만 호출되니까 엄청 빨라졌다.

2016년 4월 21일 목요일

1509 - 팰린드롬 분할

https://www.acmicpc.net/problem/1509
$dp$[$i$] = $i$번째 위치에서 가능한 팰린드롬 분할의 최소 개수
$isPaline$[$i$][$j$] = $i$~$j$ 가 팰린드롬인가
예제에도 끼워져있지만 AABDBADD 와 같은 경우의 처리때문에 여러 경우를 탐색해야한다. 이것을 분할하는 경우는 아래와 같다.
A - A - B - D - B - A - D - D
A - A - B - D - B - A - DD
A - A - BDB - A - D - D
A - A - BDB - A - DD
A - ABDBA - D - D
A - ABDBA - DD
AA - B - D - B - A - D - D
AA - B - D - B - A - DD
AA - BDB - A - D - D
AA - BDB - A - DD
팰린드롬으로 최대한 묶은 후, 남은 문자열에 대해서 이 작업을 반복한다.

검색 기능 추가

왼쪽 상단에 검색이 이미 있었지만, 오른쪽 네비게이션에도 추가해봤다.

차이점은
왼쪽 상단 검색은 검색 결과와 매칭되는 포스팅이 전부 나오고
오른쪽 검색은 구글에서 검색된 결과와 연결되어 있는 것 같다. 제목와 간단한 내용들만 리스트 형태로 나온다.

2624 - 동전 바꿔주기

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

작은 돈에 대해서 만들어질 수 있는 가지 수를 구하고, 그 가지 수들에 또 다른 동전을 추가하면 얼마나 더 만들 수 있는지를 추가하였다.
$dp$[$N$][$K$] = $N$번째 동전까지로 $K$원을 만들 수 있는 가지 수
N번째 동전마다, 이전의 K원에다가 (N번째 동전의 개수)만큼 더해보면서 반복하면 된다.
예를 들어, 입력이 아래와 같다면
10
3
3 2
5 1
1 3
1원으로 0, 1, 2, 3원을 1개씩 만들 수 있을 것이다. (최대 3개 사용)
여기에 3원을 0개 추가하면 0+0, 1+0, 2+0, 3+0원을 만들 수 있고, 1개 추가하면 3, 4, 5, 6원을. 2개 추가하면 6, 7, 8, 9원을 만들 수 있다.
이런식으로 각 단위마다 가지 수를 누적하면서 살피면 dp[N][만들고자 하는 돈] 에 정답이 들어있을 것이다.

위 예시의 정답은 1 (1원 2개, 3원 1개, 5원 1개) 이다.

2016년 4월 20일 수요일

C/C++ 연산자 우선순위

우선순위연산자설명결합방향
1::Scope resolution (범위 확인)좌 → 우
2++ --후위 증가와 감소
()함수호출
[]배열 첨자
.참조로 요소 선택
->포인터를 통해 요소 선택
3++ --전위 증가와 감소우 → 좌
+ 단항 덧셈, 뺄셈
! ~논리 NOT, 비트단위 NOT
(type)타입 캐스트
*역참조
&주소값
sizeofSize-of 연산자
newnew[]동적 메모리 할당
deletedelete[]동적 메모리 해제
4.*
->*
멤버 접근좌 → 우
5* / %곱셈, 나눗셈, 나머지
6+ 더하기, 빼기
7<< >>비트 왼쪽 쉬프트와 오른쪽 쉬프트
8< <=관계 연산자 < 와 ≤
> >=관계 연산자 > 와 ≥
9== !=관계 = 와 ≠
10&비트 AND
11^비트 XOR (exclusive or)
12|비트 OR (inclusive or)
13&&논리 AND
14||논리 OR
15?:삼항연산자우 → 좌
=직접 할당 (C++ 클래스를 위해 기본 제공)
+= −=합과 차 할당
*= /= %=곱, 몫, 나머지 할당
<<= >>=비트 왼쪽 쉬프트와 오른쪽 쉬프트 후 할당
&= ^= |=비트연산 AND, XOR, OR 연산 후 할당
16throw(예외를 위한)Throw 연산자
17,콤마좌 → 우
숫자가 낮을수록 먼저 계산한다. (연산자 우선순위 표)

연산자 우선순위때문에 코딩미스가 자주 나타나곤 한다. 이제까지 코딩하면서 이런 우선순위때문에 ~얻거나 잃은~ 겪어본 것들을 적어보고자 한다.

1. &&|| 같은 경우에는 좌에서 우로 연산을 살피기 때문에 런타임 오류(divide by zero, out of range 등)을 예상하여 막을 수 있다.
 예를 들면, if(n >= 0 && arr[n] == 1) return 0; 과 같은 코드는 n이 음수일 때는 n >= 0 이 false 이므로 더 이상 조건을 확인하지 않는다. 즉, arr[음수] 인 경우가 없으므로 out of range는 일어나지 않는다. OR연산인 || 역시 중간에 true인 조건이 확인되면 마찬가지로 더 이상 확인하지 않는다.

2. << 과 같은 쉬프트 연산은 사칙연산보다 우선순위가 낮기 때문에 $2^n$ 꼴을 쉬프트로 표현하려면 괄호를 적절히 사용해야한다.
 printf("%d", 1<<2+1); 의 출력값은 5가 아닌 8이다.

3. printf는 우에서 좌로 해석한다. (단, C99에서. 이 링크에 의하면, C++에는 순서가 정의되어 있지 않고 컴파일러의 최적화에 따라 다르다고 한다.) 아래 코드의 출력값을 예상해보자.
main(){
    int a=1, b=8, c=4;
    printf("%d %d %d", ++a+c, b/a, b*c++);
}
결과는 6 4 32 가 아닌 7 8 32이다.
그 이유는 printf 함수는 가변 인자를 받아서 인자의 개수를 모르기 때문이다.

4. 타입 캐스팅은 자료형이 작은 쪽에서 큰 쪽으로 일어난다.
  • int + int = int
  • long long + int = long long
    • ex) long long r = 15 + INT_MAX 는 오버플로우지만, long long r = 15LL + INT_MAX 는 잘 들어간다.
  • int + double = double
    • ex) int를 double로 변환할 때 쓰면 편하다. (int)50+(double)0.0 은 (double)50.0로 변환된다.

5. 연산의 우선순위는 분명 존재한다. 하지만 잘 작동할 수 있다.
격자무늬를 표현하는 r%2^c%2 라는 코드는 XOR(^)의 우선순위가 mod(%)보다 낮음에도 (r%2)^(c%2) 처럼 잘 작동한다.
3*k++ 과 같이 모호한 코드는 작성하지 않는 것이 가장 좋은 방법이다.

마지막으로, 이 모든 내용은 컴파일러마다 다를 수 있다. 그리고 명시적인 표현의 여부에 따라 다를 수 있다.
작성된 코드가 의도와 같게 작동하지 않을 때, '이럴 수도 있다' 정도의 지식으로만 참고하면 좋을 것 같다.

잘못된 내용이 있다면 지적해주시면 감사하겠습니다.


5430 - AC

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

배열이 뒤집혀도 배열의 첫번째 숫자를 버립니다. 다시 말하면, 배열의 마지막 숫자를 버리는 것은 배열이 뒤집혔을때 버리는 것과 같다.

뒤집기 연산이 들어올때마다 "앞에서 버릴 지, 뒤에서 버릴 지"를 번갈아주도록 하면 된다.

pop_front 와 pop_back 을 위해 데크를 사용한다.

같이 보기

2016년 4월 13일 수요일

3077 - 임진왜란

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

주어진 사건들의 이름에 대응되는 인덱스들만 저장해서 나중에 $O(N^{2})$ 만큼 돌면서 크기가 $i$번째 이후 중에서 $i$번째보다 큰 인덱스만 세려고 했다.

자료구조 map을 써서 각 사건들의 인덱스를 저장한 후, 사건이 입력될 때마다 j=i+1~N 의 반복문에서 index[ 사건[i] ] < index[ 사건[j] ] 를 썼더니 map에서 조회 연산이 $O(NlogN)$ 이라 그런지 시간초과를 먹었다. (당시에는 map에서 조회하는 연산을 생각하지 못해서 30분 정도 삽질한듯.. 생각나는 대로 코딩하는 자의 최후)

11581 - 구호물자

https://www.acmicpc.net/problem/11581
2015 인하대학교 프로그래밍 경시대회 G번

처음에는 BFS를 돌면서 다시 방문하는 정점이 있는 경우 NO CYCLE을 출력하고 끝내려했는데, 코딩 미스인건지 오답을 맞았다. (이거 BFS로는 안되는건가요? 누가 댓글로 답변 바람) (참고로 다들 DFS로 푼 것 같다..)

딱히 좋은 아이디어는 안 떠올라서 플로이드 와샬로 정점과 정점이 이동 가능한지 저장했다. 그리고 1번 정점에서 $i$번 정점까지 방문 가능한 것들 중에 $i$번 정점에서 $i$번 정점으로 다시 돌아올 수 있는 (싸이클이 생기는) 경우가 있다면 CYCLE을 출력하도록 했다.

입출력 몇 개를 예로 적어놔야겠다.

예제 #1
6
2 2 3
2 4 6
1 4
1 5
1 3
CYCLE

예제 #2
6
2 2 6
1 6
1 4
2 2 5
1 3
NO CYCLE

2016년 4월 11일 월요일

10888 - 두 섬간의 이동

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

다리를 N-1개 지을때마다 그 때까지의 정부가 원하는 2개의 값 현황을 알려줘야한다. 정부가 원하는 값 2개는

  • 두 섬 간에 왕래가 가능한 섬들 (i,j) (i<j) 쌍들의 개수
  • 두 섬 (i,j)가 왕래 가능할 때 섬 i에서 섬 j까지 가기 위해 이용해야 하는 최소 다리 개수의 합

와 같다. 원하는 값을 설명하기 너무 기니까 왕래 가능한 쌍들의 개수를 pairs, 섬 들이 서로 이동하는데 필요한 최소 다리 개수의 합을 bridges라고 하겠다.

이 문제 역시 서로소 집합(Disjoint Set)으로 해결할 수 있다. pairs는 서로 연결된 섬들의 개수를 통해 알 수 있다.
서로 연결된 섬들의 개수를 $x$라 하면 $x=4$일 때 (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4) 로 6개이다.
i번째에서 i<j인 개수만큼 더하므로 $$ pairs = \sum_{k=1}^x k$$ 로 나타낼 수 있다.

그럼 bridges는 이러한 pairs개 만큼의 쌍들이 x-1개, x-2개, ..., 1개만큼 떨어져있으므로 전부 더한 값이다.
예를 들어 자세히 설명하자면, 섬 4개에 번호를 붙여서 1-2-3-4 라 하면, 1에서 나올 수 있는 쌍은 ~2, ~3, ~4까지이고 각각 최소 다리의 개수는 1, 2, 3 이므로 1에서 출발하는 경우는 1+2+3=6 이다. 2에서 출발하는 경우는 1+2 이고, 3에서 출발하는 경우는 1 (3-4. 1개)이다. 그럼 섬이 4개일 때 bridges는 1+(1+2)+(1+2+3)=10 이다.

수식으로는 $$\sum_{k=1}^{n-1} \left(\sum_{i=1}^k i\right) = \frac{(n-1)n(n+1)}{6}$$ 가 된다.

그리고 갈라져있던 두 집합이 합쳐지는 경우가 있는데, 이 때는 각 집합에서의 pairs와 bridges를 빼고 합친 후의 pairs와 bridges를 더해주면 전체 값은 유지되면서 갱신한 후에 센 값과 같다.

다음은 코딩할 때 사용한 샘플 입출력이다.

예제 입력
5
1 2 4 3

예제 출력
1 1
3 4
4 5
10 20

4195 - 친구 네트워크

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

네트워크의 구조와 상관없이 몇 명이 존재하는 지만 확인하면 되기 때문에 서로소 집합(Disjoint Set)으로 해결할 수 있다.

사용자의 아이디가 대소문자의 최대 20자라길래 $(26+26)^{20}$ 이면 long long으로 변환하면 편하겠거니 했는 데, 서로소 집합에서 번호를 나타내려면 이름마다 번호를 하나씩 붙이는 게 나을 것 같았다.

네트워크를 만들고 합치는 것은 간단하다. root배열을 각 원소들이 속해있는 집합의 번호라고 했을 때 p번과 q번을 합치려면 아래와 같다.
int root[100001];

int find(int k){
    if(k == root[k]) return k;
    return root[k] = find(root[k]);
}

void merge(int p, int q){
    p = find(p);
    q = find(q);
    if(p != q) root[q] = p;
}
네트워크에 속해있는 원소들의 수는 어떻게 세야할까. 위 코드대로라면 원소는 대충 아래와 같이 있을 것이다.

[그림 1]
화살표로 가리키는 것은 부모-자식의 관계가 아니라 집합의 번호이다. 위처럼 두 집합은 초록색 원소가 그 집합의 대표라고 할 수 있다. 그럼 집합의 개수는 초록색 원소 위에 있는 숫자라고 하자.

(q가 p에 흡수되는) 위 코드를 참고하여 두 집합을 합치면 [그림 2]와 같이 나타낼 수 있다.

[그림 2]
q의 개수를 p에 더해주고, q는 1개(나중에 다른 집합으로 옮겨질 것을 우려한다면)로 바꿔주면 된다.
나머지 원소들의 집합 번호를 바꾸지 않아도 되는 것은, 나중에 조회할 때 find(e) 를 해주면 다시 갱신되기 때문이다.

서로 다른 이름이 N개의 줄마다 2개씩 나올 수 있으므로 배열의 범위는 $2N$으로 설정했다.

2016년 4월 10일 일요일

Google code jam - Qualification Round 2016

https://code.google.com/codejam/contest/6254486/dashboard
Google code jam - Qualification Round 2016 풀이

Problem A - Counting Sheep

N이 주어지면 N, 2N, ..., kN까지 진행했을 때, 0~9을 모두 사용하게 되는 시점 k에서의 kN을 구하는 문제이다.

문제 그대로 시뮬레이션하면 된다. large set에서 범위가 $0 \le N \le 10^6$ 이지만 0~9가 모두 나오게 되는건 최대 100배이므로 int 범위로 충분히 표현할 수 있다.

Problem B - Revenge of the Pancakes

앞에서부터 k번째까지를 뒤집을 수 있다. (0~k 를 k~0으로 뒤집고 모든 -를 +로 뒤집는다. +-- 를 전부 뒤집는다면 ++- 이 된다.) 최소 몇 번을 이런 식으로 뒤집으면 +로만 이루어진 문자열을 만들 수 있을까?

small set은 재귀로 구현했으나 코딩이 미숙하여 계속 틀렸다. 각 문자열을 1, 2, ..., n번까지 뒤집으면서 BFS를 진행하였다. small set은 길이 $S \le 10$ 이므로 모든 경우의 수는 $2^S$ 라서 최대 1024개만 탐색할 것이다.

small set의 정답을 들여다보고 large set을 해결할 수 있었다. 다음 문자열들은 모두 같은 연산 횟수를 가진다.
++---
+++--
+--
+-
+++-
그러면 문제를 분할할 수 있다. 위 2개의 합은 세번째의 결과와 같다.
+++---
+--
+++---+--
연속되어 있는 문자열은 하나로 생각해도 무방하다. (뒤집는 과정을 생각하면 연속되어 있는 것은 한번에 뒤집는 것이 좋다는 걸 알 수 있다.) 그렇다면 -+ 또는 +- 들만 계산하면 된다.

- 로 시작하는 경우는 처음에 등장한 - 를 뒤집고 나머지를 계산하면 된다.

Problem C - Coin Jam (small)

2진수의 길이가 N인 1~~~1의 형태(~는 0 또는 1)를 가진 10진수를 2, 3, ..., 10진수로 해석한 모든 수가 소수가 아닌 것들을 J개 출력하는 문제이다.

small set은 단순 시뮬레이션으로 해결했다.

N=16, J=50인 경우의 결과를 보면 답이 3 2 5 2 7 2 3 2 11가 자주 등장하는 데, 각 진수들이 3 2 5 2 7 2 3 2 11로 나뉘는 경우들을 출력하면 large set(N=32, J=500)도 해결된다고 한다. (Big-Integer를 사용)

Problem D - Fractiles

문제 이해 못함

2016년 4월 6일 수요일

1613 - 역사

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

입력으로 주어지는 사건들의 관계를 방향그래프로 생각하면 사건 A와 사건 C 사이에 A->B->C 의 순서가 되는 사건 B가 있으면, 사건 C는 사건 A 이후에 발생했다는 사실을 알 수 있다.

플로이드 와샬을 통해 각 사건들의 관계를 모두 구하면 s줄에 걸친 물음에 대답할 수 있다.

9322 - 철벽 보안 알고리즘

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

제 1 공개키와 제 2 공개키를 비교하여 위치가 어떻게 바뀌는 지 저장하고 암호문은 그 반대로 위치를 참조하여 출력하도록 했다.

4900 - 7 더하기

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

코드로 된 입력을 3자리씩 끊어서 0~9 중 해당하는 숫자로 변환한 후 연산하고 다시 코드로 변환했다.

2660 - 회장 뽑기

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

친구의 친구 사이는 친구이므로, 각 사람들에 대해 서로 가장 가까운 정도를 구할 수 있다.

구해진 가까운 정도(최단 경로)들이 가장 작은 사람들의 리스트를 만들어 출력한다.

1977 - 완전제곱수

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

M 이상이 되는 제곱수를 찾은 후, N 이하가 될 때 까지 나오는 제곱수를 모두 더한다.

2016년 4월 5일 화요일

2705 - 팰린드롬 파티션

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

7을 팰린드롬 파티션으로 표현하면 아래와 같다.

       7
   1+  5  +1
   2+  3  +2
  1+1+ 3 +1+1
  3+   1   +3
1+1+1+ 1 +1+1+1

가운데를 축으로 보고, 양쪽으로 갈라지는 수에 대해 다시 재귀적으로 그것들을 축으로 센다.

아래와 같은 점화식으로 표현 가능하다.
$$ f(n) = 1 + f(0) + \dots + f(n/2) $$
1은 자기 자신을 나타내는 가짓 수이기 때문에 매번의 분열마다 더해준다.

1730 - 판화

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

주어진 명령에 따라 팔을 움직이면서 자취를 그린다.

이미 그 곳에 자취가 그려져있는데 다른 방향이라면 + 를 그린다.

9518 - 로마 카톨릭 미사

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

다른 사람 소스를 보니까 내가 너무 어렵게 생각했던 것 같다.

(i, j)에서 주변 각 8방향에 대해 악수를 했다/안했다로 xxxxxxxx의 비트로 저장해서 주변 8방향을 하나씩 악수했다. (비트를 참고하여 이미 악수했다면 횟수로 세지 않았다.)

1507 - 궁금한 민호

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

(연결된 정점을 x-x 로 표현하겠다)
i-j-k 가 가능한 i-k 가 있다면 i-k 인 간선은 필요가 없다. 왜냐하면 i-k 는 i-j, j-k 로 표현이 가능하고, 같은 거리로 더 많은 도시를 갈 수 있도록 유지되기 때문이다.
결과적으로 필요한 간선만 남게 된다.

불가능한 경우는 잘못된 입력이 주어지는 경우이다. 이를테면 주어진 입력으로 a->b->c 를 해보면 a->c 보다 더 작게 나온다던가 그런 입력.

1445 - 일요일 아침의 데이트

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

다익스트라에서 선택해야할 우선순위 조건이 다음과 같이 2가지이다.
  1. 지나가는 쓰레기의 수는 최소로
  2. 쓰레기 근처를 지나는 칸의 수를 최소로
S에서 F까지 가면서 위 2가지의 가중치가 최소가 되게 선택하면서 진행하면 된다.

10217 - KCM Travel

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

주어진 비용으로 갈 수 있는 1번~모든 노드의 최단 거리를 구한다.

구하는 과정에서 아래와 같이 정보를 저장한다.
dp(i, k) = i번 노드까지 k의 비용으로 갔을 때의 최소 시간
주어진 비용 내에서 N번 노드까지 간 최소 시간을 구하면 된다.

1261 - 알고스팟

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

2차원 평면에서 큐를 넣고 빼고 하는 코드를 적으면 왠지 귀찮을꺼같아서 각 칸을 노드처럼 썼다. 예를 들면, 각 칸의 노드 번호는 아래와 같다.
// 4x2 크기의 평면
0123
4567
1인 칸으로 가는 경우에는 벽을 부숴야하므로 가중치가 1인 간선이 있다고 생각하면 된다. (그 외에는 가중치가 0인 간선)

그럼 다익스트라로 0번 -> h*w-1번 으로 가는 최단 경로 문제가 된다.
같이 보기
 - 알고스팟: BOJ

2611 - 자동차 경주

다익스트라에서 큐의 우선순위를 "가중치가 높은 노드"로 바꾸면 된다.

중간에 시작 노드를 지나갈 수 없으므로 (처음을 제외한) 시작 노드 이후의 경로는 탐색하지 않도록 한다.

경로 출력은 큐에 넣는 작업을 할때마다 그 때의 이전 노드를 따로 저장 (즉, 어디서부터 왔는 가를 저장)하여 마지막엔 시작 노드로부터 그 역순으로 따라올라가면 경로를 얻을 수 있다.

2082 - 시계

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

0~9까지 표현되는 샘플을 만들고, 시계에는 불이 켜져있는 데 샘플은 꺼져있다면 그 숫자는 대상에서 제외한다. (시계에서 꺼져있는건 무시해도 된다)

시계가 뒤집어져있다거나 잘못된 시간(ex. 28:00) 등의 입력은 없는 것 같다.

1174 - 줄어드는 수

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

나올 수 있는 가장 큰 값은 9876543210 (10자리) 이다.
1자리 수(0~9)부터 10자리 수에 대해서 각각 감소하는 수를 모두 구하면 된다.
n자리로 이루어진 모든 감소하는 수는 재귀로 구현했다.
유사한 문제
- 1038번: 감소하는 수

게시글 목록