10820 문자열 분석, fgets 주의사항

fgets로 받는 경우 입력 문자열의 최대길이가 100이므로 개행('\n')과 NULL값까지 고려해서 char 배열을 102로 잡아줘야 한다.  str[102]

그런데 틀려서 보니...
fgets(str, 100, stdin)에서... fgets를  쓰면 개행('\n')까지 받기 때문에, 최대 100자까지가 아닌 101자까지 받도록 해야 한다...
fgets(str, 101, stdin);

아 그런데 또 틀렸다...
직접 테스트 해보니.. fgets(str, 11, stdin)으로 할 경우 10글자까지만 저장된다. 개행('\n')도 저장되지 않고 딱 10글자만 저장된다. (개행까지 저장되려면 9글자를 입력해야 한다.)
결국 저 11이라는 숫자는 문자열의 NULL값까지 포함한 길이인 것 같다.
그렇기 때문에 fgets(str, 102, stdin)으로 해줘야 통과할 수 있을 것 같다.
그렇게 고쳐서 제출했더니 AC를 받았다....

백준 1008 A/B

https://www.acmicpc.net/board/view/2432

정답과의 차이가 1e-9이하이면 정답인 문제
출력되는 소수의 범위를 늘려야 한다.

float로 하면 6자리정도까지만 정확하기 때문에 틀리게 된다.
double(%lf)를 이용해야 한다.

백준 1002 터렛

주의사항

(x1, y1)과 (x2, y2)가 같은 경우도 생각해야 함!
원 하나가 다른 원 하나를 포함하는 경우도 생각해야 함. 포함하여 접점이 1개일 수도 있고, 포함해서 접점이 없을 수도 있다.

근데 이 모든 것을 간단하게 처리하는 방법도 있다.

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int main(void) {
    int t;
    scanf("%d", &t);
    while(t--) {
        double x1, y1, x2, y2;
        double dist[3];
        scanf("%lf %lf %lf %lf %lf %lf", &x1, &y1, &dist[0], &x2, &y2, &dist[1]);
        dist[2]=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
        sort(dist, dist+3);
        if(dist[0]==0 && dist[1]==dist[2]) {       
            printf("-1\n");
        }
        else if(dist[2]>dist[1]+dist[0]) {
            printf("0\n");
        }
        else if(dist[2]==dist[1]+dist[0]) {
            printf("1\n");
        }
        else {
            printf("2\n");
        }
    }
    return 0;
}

13458 시험 감독 풀이

이 문제에서 주의해야 할 점 (코드의 주석 참조)

1. 총감독관은 반드시 1명 있어야 한다. (없어도 안되고, 2명 이상이 있어도 안된다.)

2. 부감독관은 있어도 되고 없어도 된다.

3. 최악의 경우(N: 1,000,000 , Ai가 모두 1,000,000, B: 1, C: 1 인 경우) 필요한 감독관의 수가 1,000,000 * 1,000,000 명이 될 수 있으므로 int형 변수를 이용해 결과를 출력할 경우 틀리게 된다.

풀이

먼저 총감독관은 각 방마다 무조건 1명씩 있어야 하므로 N명이 필요하다.

이제 각 방에서 감시해야할 응시자 수는 Ai - B 가 된다.

나머지 시험 응시자들은 부감독관들이 모두 감시해야 한다.

각 방의 (Ai - B) 값을  "부감독관이 감시할 수 있는 응시자 수"로 나누어 주면,

각 방에 남은 응시자들을 모두 감시하기 위해 필요한 부감독관의 수를 구할 수 있다.

단, 이 때 나누어 떨어지는 경우는 괜찮지만 그렇지 않는 경우에 1을 더해줘야 하는 번거로움이 있는데, 이 부분은 C - 1을 더해서 나누어 줌으로써 편하게 계산할 수 있다. 

코드

#include <cstdio>

// long long을 편하게 사용하기 위해 llint로 설정

typedef long long llint; 

// N(시험장의 수), 

// B(총 감독관이 한 방에서 감시할 수 있는 응시자의 수), 

// C(부감독관이 한 방에서 감시할 수 있는 응시자의 수)

int n, b, c; 

// 각 시험장에 있는 응시자의 수를 저장할 배열

int a[1000000]; 

// 정답을 저장할 변수(필요한 감독관 수의 최소값, long long 형)

llint ans = 0;

int main() {

// 시험장(방)의 개수를 입력받는다.

scanf("%d", &n);

// 각 방에 있는 응시자 수를 입력받는다.

for(int i = 0; i < n; i++) {

scanf("%d", &a[i]);

}

// 한 방에서 감시할 수 있는 응시자 수를 입력 받는다.(총감독관, 부감독관)

scanf("%d %d", &b, &c);

// (1) 총감독관

// 총 감독관이 감시할 수 있는 응시자 수를 뺀다.

// 뺄 때, 음수가 되지 않도록 조건이 필요하다.

for(int i = 0; i < n; i++) {

if(a[i] >= b)

a[i] -= b;

else //(방의 인원 < 감시할 수 있는 응시자수)인 경우

a[i] = 0;

}

// 총감독관은 반드시 각 방에 1명씩 필요하므로 총 N명이 반드시 필요하다.

ans = n;

// (2) 부감독관

// 정수형 나눗셈이므로 나누어 떨어지지 않으면, 

// 몫에 1을 더한 값이 응시자들을 모두 감시하기 위해 필요한 부감독관의 수가 된다.

// 하지만 그렇게 하지 않아도, c - 1을 더해주고 나누면 

// 나누어 떨어지는 경우, 그렇지 않은 경우 모두 올바르게 답을 구할 수 있다.

for(int i = 0; i < n; i++) {

ans += (llint)((a[i] + c - 1) / c);

}

// long long형이므로 %lld로 출력해준다.

printf("%lld\n", ans);

return 0;

}

BOJ 2169 로봇 조종하기

N * M 배열에서 로봇은 왼쪽, 오른쪽, 아래쪽으로만 이동이 가능하다. 그리고 한 번 탐사한 지역은 다시 탐사하지 않도록 한다. 그리고 각 배열의 칸에는 숫자(-100 ~ 100)가 적혀있는데, 이 때, (0, 0)에서 (N - 1, M - 1)까지 이동하면서 지나간 칸의 숫자의 합이 최대가 되도록 이동하고, 그 최대값을 구하는 문제이다.

dp를 이용해서 구할 것인데, 예를들어, (r, c)에서 출발해서 (N - 1, M - 1)칸 까지의 칸의 숫자의 합을 구할 때, (r, c - 1), (r, c + 1), (r + 1, c) 칸 중 어느 칸으로 이동해야 숫자의 합이 최대가 되는 경로인지 볼 것인데, 단순히 (row, column) 정보로는 부족하다.

같은 (r, c - 1)라고 해도 직전 경로가 위인지, 왼쪽인지, 오른쪽인지(어디에서 왔는지)에 따라 다음에 갈 수 있는 경로가 다르게 결정된다. 예를들어, 왼쪽에서 왔다고 하면 한 번 탐사한 지역은 다시 탐사하면 안되기 때문에 오른쪽이나 아래쪽으로 가야한다. 그래서 어떤 방향에서 왔는지에 대한 정보가 필요하다.

그리고 dp를 이용해서 풀 때, 평소 dp배열을 -1로 초기화하고 -1이 아니면 답을 구했다고 판단하고 리턴해줬는데, 이 문제의 경우 데이터에 음수값이 있기 때문에, 따로 boolean check배열을 만들어서 이미 그 부분에 대해 답을 구했는지 아닌지 판단한다.

그리고, 또 실수할 수 있는 부분이 있다면, 최대값을 구할 때, max값을 0으로 초기화해놓고, 비교해서 최대값을 구하는 것에 익숙한데, 위에서 말했듯이 음수값이 있기 때문에 0으로 초기화하면 안되고, 모든 입력이 -100으로 들어온다고 가정하고 그에 해당하는 1000 * 1000 * (-100) 으로 max값을 초기화 해줄 필요가 있다.
아니면, 그냥 max값에 바로 구한 값을 대입하면서 시작하는 방법도 있다. 이 방법은 굳이 나올 수 있는 최소값이 얼마일까 고민할 필요도 없고, 그렇기에 실수할 가능성도 적다.

BOJ 14590 KUBC League (Small)

주어진 입력값으로 그래프를 만들었다.
그리고 모든 가능한 경우를 다 확인하고 그 중 최대값을 구한다고 하면...
아마도 n! 만큼의 시간이 걸릴 것이다.

그래서 dp로 접근하기로 했다.
먼저 그래프는 1번vertex부터 시작해서 1번이 이긴 vertex로, 한 vertex에서 그 vertex가 이긴 vertex로... 이렇게 단방향으로 연결되어 있는 directed graph이다.

선수의 나열은 각 선수가 달라야 하므로 방문한 vertex는 다시 방문하면 안되고, 그렇기 때문에 방문한 vertex에 대한 기록이 필요하다. 다행이 n제한이 최대 20이라, 비트마스크를 이용해 상태 dp를 이용할 수 있다.

d[node][state] = 지금까지 방문한 점이 state이고, node에서 시작해서 얻을 수 있는 선수 나열의 최대 길이

d[node][state] = Max( d[next][state | (1<<next) ) + 1

지금까지 방문하지 않은 점 next들을 방문해보면서 그 중 최대인 값을 얻으면 된다.

근데 문제가 하나 더 있다. 바로 선수 나열의 최대길이 뿐 아니라, 선수 나열이 어떤식으로 되어있는지도 구해서 출력해야 한다.

이 부분도 좀 까다로웠는데, 처음에는
nextNode[node] = node의 다음 vertex(node)
로 놓고, Max값이 갱신될 때 nextNode[node]값을 구했는데(갱신했는데), 이럴 경우 문제가 생기는 것 같다.

node와 그에 따른 여러 state의 경우의 수가 존재하는데, 정답에 해당되는 경우가 여러 개일 수 있고, 각 경우마다 nextNode[node]값이 갱신되면 정확한 경로가 나오지 않을 수 있다.

그래서 고민하다가,
nextNode[node][state] = 지금까지 방문한 점이 state일 때, node의 다음 vertex
로 놓고, 나중에 답을 출력할 때, state도 처음부터 시작하여 다음 node에 따라 변경해주면서 선수의 나열을 출력했다. 가장 안전해 보이면서도 좀 무식한? 방법같은데 다른 방법이 떠오르지 않아서... 일단 이렇게 했다.

그리고 추가로...좀 많이 틀리고, 고민을 했는데,
결정적인 이유가 바로 배열의 크기 설정에 있었다. 상태가 0 ~ (2의 20제곱 - 1) 까지 존재하기 때문에 배열에서 다 커버해 줘야 하는데, 나는 배열의 크기를 (2의 20제곱 - 1)로 잡아
0 ~ 2의 20제곱 - 2까지만 커버했고, 그래서 printf를 이용해 디버깅할 때, 도무지 이해할 수 없는 출력 결과가 나왔다. 거의 10시부터 시작해서 새벽 3시까지 고민하다가 오전에 다시 고민해서 배열의 크기 설정이 원인이란 사실을 겨우 발견했다. 감사합니다...

그리고 내 방법은 메모리와 시간 모두 매우 크게 나와서 상위권에 있는 고수님들의 코드를 보려고 한다.

풀이도 보려고 한다. : https://www.acmicpc.net/board/view/15506

BOJ 1219 오민식의 고민

어렵다.
Bellman-Ford algorithm을 사용하면 되긴하는데, 출력 조건에 맞춰 출력하는 부분에서 Bellman-Ford algorithm과 이 문제에 대한 깊은 이해가 필요하고 많은 고민이 필요해 보인다.

판별해야 하는 상황은 다음과 같다.
1. 도착도시에 도착하는 것이 불가능할 때
2. 무한대의 돈을 벌 수 있을 때
3. 도착도시에 도착하는 것이 가능하면서 무한대의 돈을 버는 것은 아닐 때

다음과 같이 판별해볼 수 있겠다.
1. 출발도시에서 도착도시까지 도달하는 것이 불가능하다면 upper값으로 설정한 NEGINF에 100만씩 100번 완화할 수 있으므로 upper[des]값이 NEGINF인 경우만 도달 불가능하다고 보면 안되고, NEGINF+100*1,000,000 이하인 경우를 도달 불가능하다고 봐야할 것이다.
- JM book 참고하기

2. 단순히 양수 사이클이 있는 경우라고 생각하기 쉽다. 하지만 아니다.
양수 사이클이 존재하면서 그 양수 사이클에서 도착도시까지 갈 수 있어야 한다.
양수 사이클이 존재하지만 양수 사이클에서 도착도시로 갈 수 없다면 돈을 벌 수 없기 때문에 그 경우는 양수 사이클로 가지말고 도착도시로 가야한다.

3. 사이클이 없거나, 사이클이 있더라도 그 사이클에 빠지면 도착도시로 갈 수 없는 경우이다.

** 2, 3을 구별해서 하는 것이 문제이다. 사실 이것들을 생각하지도 못했는데, 질문 게시판에 있는 고수들의 질문과 답변을 보고 알았다.


실제 테스트할 때는,
4 0 3 4
0 1 0
1 2 0
2 1 0
0 3 10
10 10 10 10 으로 테스트 해보면 된다.









만약 사이클이 있고 그 사이클에서 도착도시까지 연결돼 있다면 n번째 갱신할 때, 도착도시까지 가는 경로가 갱신될 줄 알았는데... 이 예제를 보면 그렇지 않다는 것을 알 수 있다!

사이클이 있는지는 판단하기 쉽지만, 그 사이클에서 도착도시까지 갈 수 있는지 없는지를 판단하기가 어렵다. 어떻게 해야할까?

일단 사이클이 있다면 n번째 갱신할 때, 사이클에 포함된 도시가 갱신될 것이다. 그럼 그 도시부터 시작해서 도착도시까지 갈 수 있는지 dfs로 알아보면 될 것 같다. -> 생각해보니 n번째 갱신할 때 사이클에 포함되지 않은 도시도 갱신될 수 있을 것 같다... 그럼 어떻게 사이클에 포함된 도시를 알 수 있을까? -> 잘 모르겠지만, 이 문제에서는 사이클에 포함된 도시를 골라낼 필요가 없다. n번째 갱신할 때, 갱신되는 도시중에는 사이클에 포함되지 않은 도시도 있겠지만, 그 도시는 사이클로부터 온 도시일 것이다. 결국, n번째 갱신할 때 갱신되는 도시가 어떤 도시든 그 도시에서 도착도시까지 갈 수 있다면, 사이클에서 도착도시까지 갈 수 있는 것이다....

그리고, 사이클이 있으면 시작도시에서 사이클이 있는점까지 갈 수 있는지도 체크해야 한다.좀 간편하게 하기위해 플로이드와샬로 각 도시간에 이동할 수 있는지를 체크해놓는 것도 괜찮고, 아니면 벨만포드를 구현할 때, here, there가 있어서 here를 이용해서 there를 갱신하는데, here가 NEGINF(INF)인 경우(즉, 시작점에서 here까지 도달 못한 경우) 갱신이 안되게 하면, 사이클이 있어도 시작점에서 갈 수 없는 사이클이라면 사이클을 찾아낼 수 없을 것이다.
그리고 이렇게 구현하면 좋은 것이, 도착도시에 도달할 수 없는지 판단할 때 그냥 NEGINF(INF)인지 아닌지만 보면된다.
이런 구현 방식은 kks227님 블로그를 참조했다.

 그래서 난 일단 here가 NEGINF(INF)인 경우 갱신이 안되게 하고, n번째 갱신할 때 갱신되는 도가 있다면(사이클이 있다면) 갱신되는 점들 중 하나라도 도착도시와 연결이 된다면 돈을 무한히 벌 수 있는 것으로 판정할 것이다.

일단 AC를 받았다.
벨만포드에 대해 잘 알고있다고 생각했는데... 전혀 그렇지 않았고... 오히려 배웠다.
정말 공부가 되는 좋은 문제이다... 나중에 꼭 다시 풀어보기. 생각해보기.