개발자 성장일기

문제https://www.acmicpc.net/problem/2294 해설100 * 10000을 해도 100만밖에 되지 않기 때문에 그냥 풀기 코드1234567891011121314151617181920212223242526272829303132333435363738#includeiostream>#includealgorithm>#includecstring> using namespace std; const int INF = 87654321;int n,k,cost[104],ret[10004],tmp; int main(){  cin >> n >> k;  fill(ret,ret+10004,INF);   int cnt=0;  for(int i=0;in;i++){    cin >> tmp;    if(tmp=100..

문제https://www.acmicpc.net/problem/12852 해설경우의 수만 구하면 된다면 dp를 이용해서 간단하게 구할 수 있음하지만 이동 경로를 표시해야 하기 때문에 그 점을 기록하기 위한 last배열을 선언재귀를 통해 구현하였을 경우 깊이 문제가 발생하여 반목문으로 해결 코드12345678910111213141516171819202122232425262728293031323334353637383940#includeiostream>#includealgorithm> using namespace std;typedef long long ll; int n, visited[1000004],last[1000004]; void go(int num) {    visited[1] = 0;     for (..

문제https://www.acmicpc.net/problem/4811 해설dp로 풀어야 하는 문제임은 빠르게 알 수 있으나 어떻게 풀지 조금 걸린 문제온전한 알약과 반만남은 알약을 기준으로 문제를 해결 코드12345678910111213141516171819202122232425262728#includeiostream>#includealgorithm>#includecstring> using namespace std;typedef long long ll; int n;ll dp[34][34]; ll go(int full, int half){  if(full == 0 && half ==0) return 1;  ll &ret = dp[full][half];   if(ret) return ret;  if(half..

문제https://www.acmicpc.net/problem/2240 해설경우의수가 너무 커서 dp로 해결-1로 초기화 할 경우 ~ret을 사용하면 -1일때만 false를 반환하도록할 수 있음 코드12345678910111213141516171819202122232425#includeiostream>#includealgorithm>#includecstring> using namespace std; int t,w,dp[1004][2][34], mv[1004]; int go(int idx, int location, int cnt){  if(cnt  0) return -10000;  if(idx >= t) return 0;  int &ret = dp[idx][location][cnt];  if(~ret) re..

문제https://www.acmicpc.net/problem/1103 해설모든 경우의 수를 고려할 경우 (50*50)의 4제곱이 되기 때문에 dp를 이용해서 해결 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#includeiostream>#includealgorithm> using namespace std; int n,m,dp[54][54], ret;char mp[54][54];int dy[4] = {-1,0,1,0};int dx[4] = {0,1,0,-1};string line;void go(int y, int x, int cnt){  if(cnt > n*m){    ..

문제https://www.acmicpc.net/problem/17070 해설경우의 수가 16 * 16 * 3 이기 때문에 그냥 탐색으로 해결경우의 수가 더 커질 경우 DP를 이용해야함 코드123456789101112131415161718192021222324252627282930313233343536373839404142#includeiostream>#includealgorithm> using namespace std; int n, ret, mp[20][20]; void go(int y, int x, int ty){  if(y == n-1 && x == n-1){    ret++;    return;  }    if(ty != 1){    if(x+1  n && mp[y][x+1] == 0){      ..

문제https://www.acmicpc.net/problem/2098 해설단순히 모든 곳을 방문하는 문제면 간단 dp문제 이지만 순회를 해야하는 조건이 조금 까다로움순회를 확인하기 위해 비트마스킹 사용 코드123456789101112131415161718192021222324252627282930313233343536373839404142#includeiostream>#includealgorithm>#includevector>#includecstring> using namespace std; const int INF = 987654321;int n,start[20],end[20],s,e,cost, dp[20][1(16)],mp[20][20];vectortupleint,int,int>> v;vectorve..

문제https://www.acmicpc.net/problem/1072 해설n의 값이 크기 때문에 이분 탐색을 이용함 코드12345678910111213141516171819202122232425262728#includeiostream>#includealgorithm> using namespace std;typedef long long ll; ll x, y, ret =-1, tmp,low,mid,hi,z; int main(){  cin >> x >>y ;    z = (y*100)/x;    low = 1; hi = 1e9;  while(low = hi){        mid = (low+hi)/2;        if(((y+mid)*100)/(mid+x)>z){            ret = mid;  ..

문제https://www.acmicpc.net/problem/16434 해설stack에 담고 뒤에서 부터 풀면 쉽게 풀 수 있음 코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#includeiostream>#includealgorithm>#includestack> using namespace std;typedef long long ll;ll room_num, str, hp,room_type,room_str,room_hp,attack_cnt,max_hp;stacktupleint,int,int>> s; int main(){  ios_base::sync_with_stdio(false);  cin.tie..

문제https://www.acmicpc.net/problem/7795 해설최대값이 너무 크기 때문에 map을 사용하면 되는 문제 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#includeiostream>#includealgorithm>#includemap> using namespace std; mapint,int> mp;int ret,a,b,tmp; int main(){  ios_base::sync_with_stdio(false);  cin.tie(NULL);cout.tie(NULL);   cin >> a >> b;   for(int i=0;ia;i++){    cin >> tmp;    ..