게임
음 틀렸다. 왜 틀렸지 처음에는 일단 분모를 안바꿔줘서 틀렸었다.
#define _CRT_SECURE_NO_WARNINGS
#define debug 0
#include <iostream>
#include <algorithm>
#include <vector>
#include<string.h>
using namespace std;
#define NUM 100001
#define MAXV 987654321
long long int N, M, S;
int arr[NUM], brr[NUM];
vector<long long int>as, bs;
long long int T, A, B;
int X, Y, Z;
int divd(int x, int y) {
return (int)(((double)x / (double)y)*100);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
freopen("input.txt", "r", stdin);
cin >> X >> Y >> Z;
int mid, st = Y, dt = X;
mid = (st + dt)/2;
Z = divd(Y, X);
int z = divd(mid,X);
while (st < dt) {
if (z != Z) {
dt = mid;
}
//st ....<< dt 줄여도 안바뀌면
else {
st = mid + 1;
}
mid = (st + dt) / 2 ;
z = divd(mid,X + mid - Y);
}
if(Z != z)
cout << mid - Y<< "\n";
else {
cout << -1 << "\n";
}
return 0;
}
음 아무래도 divd 부분이 틀린거 같다. 나눗셈이 제대로 안된다.
#define _CRT_SECURE_NO_WARNINGS
#define debug 0
#include <iostream>
#include <algorithm>
#include <vector>
#include<string.h>
using namespace std;
#define NUM 100001
#define MAXV 1000000001
long long int N, M, S;
int arr[NUM], brr[NUM];
vector<long long int>as, bs;
long long int T, A, B;
int X, Y, Z;
int divd(int x, int y) {
return (int)(((double)x * 100 / (double)y));
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
freopen("input.txt", "r", stdin);
cin >> X >> Y >> Z;
int mid, st = Y, dt = X;
mid = (st + dt) / 2;
Z = divd(Y, X);
int z = divd(mid, X + mid - Y);
int prev = mid;
st = 0, dt = MAXV;
while (st < dt) {
//올린게 너무 크면;
if (z > Z) {
dt = mid;
}
//st ....<< dt 줄여도 안바뀌면
else {
//이게 맞는건가??
st = mid + 1;
}
mid = (st + dt) / 2;
z = divd(mid, X + mid - Y);
}
if (Z != z)
cout << mid - Y << "\n";
else {
cout << -1 << "\n";
}
return 0;
}
그게 아니라 이분 탐색 범위가 잘못됬었다. 엄청 크게 잡아도 된다. 대신 long long int로 잘 선언하자.!!
집배원 한상덕
음 지금까지 경로에 대한 문제랑은 좀 다른게 이건 가지수나 뭐 그런걸 구하는게 아니다. 피로도라고 그냥 지나온 지점의 최저점 최고점의 차이를 마지막에 알면된다.
물론 완탐하기엔 4^50이라 말이안되고, memoization으로 좀 줄일 수 있을까 생각해 봤다.
i,j 지점 까지의 최저 피로도가 되는 lo ,hi 길이를 구해봤자 그 뒤에 지나가는 지점들에 따라 이전에 선택한 피로도에 대한 고저가 최선이 아닐 수 도 있다는 것을 찾아내었다.
뭐 7~12에서 들쑥거리는 경로랑 1~3에서 들쑥거리다 4인 지점에 가면 물론 1~3이 여기까지는 최선인데, 그 이우헤 21에 10에 가게되면 7~12를 지나온 경로가 최선이 였다고 후회 하겠지.....
그래서 문제를 좀더 생각해보자.......
내가 한상덕이가 어떤 지점에서 다음 지점으로 가려하는데 다음 언덕이 현재랑 차이가 더 작은 쪽을 선택하지 않을까??
다시 문제를 보니 좀 다른 부분이, 지나온 지점을 다시 지나다녀도 되는거고, 다시 우체국으로 돌아와야 한다....!!
음 이렇게 생각하고 다시 보니, 고저가 낮은 지점의 길을 만들면 되는 느낌이다.
약간 느낌에 이렇게 하면 될거 같다. 일단 피로도가 낮은 쪽으로 선택해서 가고 지나온 지점은 vis 표시를 한다. 그러다 집에 도착하면 vis를 초기화 시켜주면 되지 않을까? 그렇게 모든 집을 방문하면 최소 피로도를 계산한다.
음 이렇게 구현하니까 이동경로가 제대로 체크가 안된다. 집 찾고 vis 0 으로 해주니까 다시 찾을때 이상한 곳으로 한다. 1행 2열로 감; 9로 왜그러지
#define _CRT_SECURE_NO_WARNINGS
#define debug 0
#include <iostream>
#include <algorithm>
#include <vector>
#include<string.h>
using namespace std;
#define NUM 51
#define MAXV 10000001
long long int N, M, S;
char arr[NUM][NUM];
int brr[NUM][NUM];
bool vis[NUM][NUM] = { 0 };
int low[NUM][NUM] = { 0 };
int high[NUM][NUM] = { 0 };
int dir_r[4] = { 0,1,0,-1 };
int dir_c[4] = { 1,0,-1,0 };
int ans = 0;
int cnt = 0;
bool isBound(int r, int c) {
if (0 <= r && r < N && c >= 0 && c < N)
return true;
else
return false;
}
void dfs(int r, int c) {
int nr, nc;
int dt_r, dt_c;
int lo, hi;
int pilo = MAXV;
if (cnt == 0) {
if(ans ==0)
ans = high[r][c] - low[r][c];
return;
}
if (arr[r][c] == 'K')
{
cnt--;
memset(vis, 0, sizeof(vis));
}
for (int i = 0; i < 4; i++) {
nr = r + dir_r[i];
nc = c + dir_c[i];
if (isBound(nr, nc) && vis[nr][nc] == 0) {
lo = min(brr[nr][nc], low[r][c]);
hi = max(brr[nr][nc], high[r][c]);
if (pilo > hi - lo) {
pilo = hi - lo;
dt_r = nr;
dt_c = nc;
low[nr][nc] = lo;
high[nr][nc] = hi;
}
}
}
vis[dt_r][dt_c] = 1;
dfs(dt_r, dt_c);
vis[dt_r][dt_c] = 0;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
freopen("input.txt", "r", stdin);
cin >> N;
int st_r, st_c;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> arr[i][j];
if (arr[i][j] == 'P')
{
st_r = i;
st_c = j;
}
else if (arr[i][j] == 'K') {
cnt++;
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> brr[i][j];
}
}
low[st_r][st_c] = brr[st_r][st_c];
high[st_r][st_c] = brr[st_r][st_c];
vis[st_r][st_c] = 1;
dfs(st_r, st_c);
cout << ans;
return 0;
}
몰랐는데 고민 3일하고 보니까 이분탐색이 풀이였다. 왜그런지는 좀있다 생각해보고
일단 내 틀린 접근법은 이거였다.
모든 가능한 길은 다 가보긴 해야한다.
지나온 길을 돌아갈 수 있다.
즉 dfs일 것이다.
그럼 시간을 줄이고 잘못된 재방문을 막자.
각 해당 지점을 지나 모든 곳을 방문시 피로도를 기록할 수 있다. -> 백트레킹
돌아 오면서 이 지점을 지나가서 모든 곳 방문시 최소 피로도를 저장한다.
지나가다 이미 피로도가 지나가는 지점 피로도 보다 높으면 이동할 필요 없다.
그런데 이동중에 방문 지점을 다시 가지 못하게 하는게 어렵다.....
무한루프 돌아 ,
vis[nr][nc] = 1;
int backtracking_pilo = dfs(nr, nc, hi, lo, cnt);
vis[nr][nc] = 0;
한 'K' 방문후 다시 돌아갈 수 가 없다.
어떤 K 방문시 각각들에 대해 피로도를 구하고 최고를 답으로하자!..... 이게 브루트 포스한 방법이다.
시간 초과났음;; 여러번 구하는걸 시간 줄이는 방법을 생각해보자!! 했는데
완탐이면서 방문한 지점 다시 가도되는데 조건부로 다시 가면 안되게 하는 방법을 고민하다 포기했다;;
** 해설을 보니 생각하지 못한 해결 방법이였따.
왜 저러게 생각하지 못했을까?
문제를 접근할때 좀 더 원론적으로 접근해야 할거 같다. 나는 이 문제가 그냥 dfs 일반 문제랑 비슷하게 생겨서 그리디한 접근 법과 완전탐색 중에서만 생각했다. 이는 문제를 겉으로만 보고 해결법을 좁힌게 문제 같다.
좀 더 근본적으로 시작해보자.
처음에 이렇게 생각하기도 했다. 내가 다른 집들을 돌아다녀야 되는데 어떤 조건에 의해서 너무 높은 산이나 낮은 곳은 가지 않는 방법은 없을까?? 이렇게 생각했었고 ,
이때 한번에 정하는 방법이 절대 없다고 생각했고 사실 그게 맞았따.
그런데 이런 해결책이 있었다. 지나 갈 수 있는 높이를 높거나 낮은 언덕을 줄이면서 확인해 보는 방법이 있다.
그런데 바로 이렇게 나올 수는 없다.
사실 아까 이렇게 생각했다. 너무 많은 길 중에 정답 길로만 갈 수 없을까? 이 길이 아니라는걸 미리 어떻게 알지?
즉 내 방법은 길을 쳐낼 생각에 집중한거라서 위에 처럼 생각 할리가 없다.
사실 오른쪽 처럼 생각했으면 좋았을 텐데 , 너무 높거나 낮은 언덕은 어쩌면 갈 필요가 없겠네에서 생각이 시작될 수 있었을까?
** 추가로 뭔가 지금 까지 푼 문제중에 집배원 한상덕이 가장 아름다운거 같다......
** 다익스트라로는 어떻게 풀지?