딩코딩 : Computer Science 블로그

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>

using namespace std;


int main() {
	//freopen("input.txt.txt","rt",stdin);
	int n,i,arr[31],order=1,pos=1,cnt=0;
	scanf("%d", &n);
	for(i=1;i<=n;i++){
		scanf("%d", &arr[i]);
	}
	stack<int> s;
	string ans = "";
	for(i=1;i<=n;i++){
		s.push(arr[i]);
		ans+='P';
		
		while(!s.empty()&&s.top()==order){
			ans+='O';
			order++;
			s.pop();
		}
	}
	
	if(s.empty()) printf("%s\n",ans.c_str());
	else printf("impossible\n");

	return 0;	
}

기차 교차로 문제

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>

using namespace std;

int main() {
	//freopen("input.txt.txt","rt",stdin);
	int n,k,i;
	scanf("%d %d", &n, &k);
	vector<int> v;
	
	
	while(n>0){
		v.push_back(n%k);
		n = n/k;
	}	
	for(i=v.size()-1; i>=0; i--){
		if(v[i]>=10){
			printf("%c", ('A'+(v[i]-10)));
		}
		else printf("%d",v[i]);
	}
	
	return 0;	
}

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>

using namespace std;

int stack[100], top=-1;
void push(int x){
	stack[++top] = x;
}
int pop(){
	return stack[top--];
}

int main() {
	//freopen("input.txt.txt","rt",stdin);
	int n,k,i;
	scanf("%d %d", &n, &k);
	char str[20]="0123456789ABCDEF";
	while(n>0){
		push(n%k);
		n = n/k;
	}
	while(top!=-1){
		printf("%c",str[pop()]);
	}
	
	return 0;	
}

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>

using namespace std;

int a[1501];
int main() {
	//freopen("input.txt.txt","rt",stdin);
	int n, i, p2, p3, p5, min=INT_MIN;
	scanf("%d",&n);
	a[1]=1;
	p2=p3=p5=1;
	for(i=2; i<=n; i++){
		if(a[p2]*2 < a[p3]*3) min=a[p2]*2;
		else min=a[p3]*3;
		if(a[p5]*5<min) min=a[p5]*5;
		if(a[p2]*2==min) p2++;
		if(a[p3]*3==min) p3++;
		if(a[p5]*5==min) p5++;
		a[i] = min;
	}
	printf("%d",a[n]);
	
	
	return 0;	
}

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int find_pos(vector<int> &v , int pos){
	while(v[pos]==0){
		pos++;
		if(pos>v.size()){
			pos = 1;
		}
	}
	return pos;
}

int main() {
	//freopen("input.txt.txt","rt",stdin);
	//     1 2 3
	// 1:  0 2 3
	// 2:  0 1 3
	// 3:  0 1 2
	// 4:  0 0 2
	// 5:  0 0 1 -> 정전 
	
	int n,i,t,pos=1,sum=0;
	scanf("%d", &n);
	vector<int> v(n+1);
	for(i=1; i<=n;i++){
		scanf("%d", &v[i]);
		sum+=v[i];
	}
	scanf("%d",&t);
	
	if(t>=sum){
		printf("-1");
		return 0;
	}
	
	while(t>0){
		pos = find_pos(v, pos);
		v[pos]--;
		pos++;
		pos = find_pos(v, pos);
		
		
		//for(i=1; i<=n;i++){
		//	printf("%d ", v[i]);
		//}
		//printf("%d", pos);
		//printf("\n");
		
		t--;
	}
	printf("%d ",pos);
	
	
	
	
	 
}

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int a[2001];
int main() {
	//freopen("input.txt.txt","rt",stdin);
	int n, k, i, p=0, cnt=0, tot=0;
	scanf("%d",&n);
	for(i=1; i<=n; i++){
		scanf("%d", &a[i]);
		tot+=a[i];
	}
	scanf("%d",&k);
	if(k>=tot){
		printf("-1\n");
		return 0;
	}
	
	while(1){
		p++;
		if(p>n) p=1;
		if(a[p]==0) continue;
		a[p]--;
		cnt++;
		if(cnt==k) break;
	}
	while(1){
		p++;
		if(p>n) p=1;
		if(a[p]!=0) break;
	}
	
	printf("%d",p);
	
	 
}

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

bool check[1001];


int findNext(int cur, int k, int n){
	int cnt = 0;

	while(cnt<k){
		if (check[cur]){
		}
		else{
			cnt++;
		}
		if(cnt==k) break;
		cur++;
		if(cur>n) cur=1;
	}
	return cur;
}

int main() {
	//freopen("input.txt.txt","rt",stdin);
	int n, k,size,i,j,idx,cnt=0,cur;
	scanf("%d %d",&n, &k);
	size = n;
	cur = 1;
	while(cnt!=n-1){
		cur = findNext(cur, k, n);
		check[cur] = true;
		//printf("%d : " ,cur);
		cnt++;
		
		
		//for(i=1; i<=n; i++){
		//	if(!check[i]){
			//	printf("x");
		//	}
		//	else printf("o");
	//	}
	//	printf("\n");
		
		
	}
	
	for(i=1; i<=n; i++){
		if(!check[i]){
			printf("%d", i);
		}
	}
	// check idx 1~n번까지 사용  
	// 1 2 3 4 5 6 7 8
	// . . o . . . . . 
	// . . o . . o . .
	// . . o . . o . .
	// o . o . . o . .
	// o . o . o o . .
	// o . o . o o . .
	// o o o . o o . .
	// o o o . o o . o
	// o o o o o o . o
	

}

-------------

강의 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
	//freopen("input.txt.txt","rt",stdin);
	int n,i, k, pos=0, bp=0, cnt=0;
	scanf("%d %d", &n, &k);
	vector<int> prince(n+1);
	while(1){
		pos++;
		if(pos>n) pos = 1;
		if(prince[pos]==0){
			cnt++;
			if(cnt==k){
				prince[pos]=1;
				cnt=0;
				bp++;
			}
		}
		if(bp==n-1) break;	
	}
	
	for(i=1; i<=n; i++){
		if(prince[i]==0){
			printf("%d\n",i);
			break;
			
		}
	}

}

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int main() {
	//freopen("input.txt.txt","rt",stdin);
	
	int n, i, m, lt=1, rt, mid,sum=0 , min=100000;
	scanf("%d %d", &n, &m);
	
	vector<int> a(n+1);
	
	for(i=0; i<n; i++){
		scanf("%d", &a[i]);
		sum+=a[i];
	}
	//printf("%d\n",sum);
	rt=sum;
	while(lt<=rt){
		mid=(lt+rt)/2;
		int cnt = 1;
		int vsum = 0;
		for(i=0;i<=n;i++){
			vsum += a[i];
			if(vsum > mid){
				cnt++;
				vsum = 0;
				i--;
			}
		}
		if(m >= cnt){
			//printf("%d %d %d\n",lt,rt, mid);
			rt = mid-1;
			if(mid < min) min = mid;
			
		}
		else lt = mid+1;
	}
	printf("%d", min);
	
	// 1 2 3 4 5 6 7 8 9
	
}

----

함수로 깔끔하게

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;


//mid 숫자에서 몇개의 바구니에 들어갈 수 있는지 알아내는 함수 
int func(vector<int> &a, int mid){
	int cnt = 1;
	int vsum = 0;
	for(int i=0;i<=a.size();i++){
		vsum += a[i];
		if(vsum > mid){
			cnt++;	
			vsum = 0;
			i--;
		}
	}
	return cnt;
}


int main() {
	//freopen("input.txt.txt","rt",stdin);
	
	int n, i, m, lt=1, rt, mid,sum=0 , min=100000;
	scanf("%d %d", &n, &m);
	
	vector<int> a(n+1);
	
	for(i=0; i<n; i++){
		scanf("%d", &a[i]);
		sum+=a[i];
	}
	//printf("%d\n",sum);
	rt=sum;
	while(lt<=rt){
		mid=(lt+rt)/2;
		int cnt = func(a, mid);
		if(m >= cnt){
			//printf("%d %d %d\n",lt,rt, mid);
			rt = mid-1;
			if(mid < min) min = mid;
		}
		else lt = mid+1;
	}
	printf("%d", min);
	
	// 1 2 3 4 5 6 7 8 9
	
}

오류 있음

----------------------------------

수정

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int a[1001], n; 
int Count(int s){
	int i, cnt=1, sum=0;
	for(i=1; i<=n; i++){
		if(sum+a[i]>s){
			cnt++;
			sum=a[i];
		}
		else sum=sum+a[i];
	}
	return cnt;
}

int main() {
	freopen("input.txt.txt","rt",stdin);
	int m, i, lt=1, rt=0, mid, res, maxx=-1;
	scanf("%d %d", &n, &m);
	for(i=1; i<=n;i++){
		scanf("%d",&a[i]);
		rt=rt+a[i];
		if(a[i]>maxx) maxx=a[i];
	}
	while(lt<=rt){
		mid=(lt+rt)/2;
		if(mid>=maxx && Count(mid)<=m){
			rt = mid-1;
			res=mid;
		}
		else lt=mid+1;
	}
	printf("%d",res);
	
}

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

//조건에 부합하는지 check하는 함 수  
bool check(int mid, int c, vector<int> &v){
	int cur =v[0];
	int cnt = 1;
	for(int i=1; i<v.size(); i++){
		if(v[i] -cur >=mid){
			cur = v[i];
			cnt++;
		}
	}
	return cnt>=c;
}

int main() {
	freopen("input.txt.txt","rt",stdin);
	int n,c,i,res;
	scanf("%d",&n);
	scanf("%d",&c);
	
	vector<int> v(n);
	for(i=0;i<n;i++){
		scanf("%d",&v[i]);
	}
	sort(v.begin(),v.end());
	
	int mid, lt=v[0],rt=v[n-1];
	
	while(lt<=rt){
		mid=(lt+rt)/2; 
		bool how = check(mid,c,v);
		if(how){
			res = mid;
			lt = mid+1;
		}
		else{
			rt = mid-1;
		}
	}
	printf("%d\n", res);
	
}

처음 짠 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int main() {
	//freopen("input.txt.txt","rt",stdin);
	
	int n,k,cnt=0;
	scanf("%d",&n);
	
	for(int i=n/2 +1; i>=1; i--){
		int sum = i;
		for(int j=i-1 ; j>=1; j--){
			sum+=j;
			
			if(sum==n){
				for(k=j; k<i;k++){
					printf("%d + ",k);
				}
				printf("%d = %d\n",k,sum);
				cnt++;
				break;
			}
			else if(sum>n){
				break;
			}
			
		}
		
	}
	printf("%d",cnt);


}

------

수정

1, 2 -> (15-3)%2==0이므로 가능

1,2,3 -> (15-6)%3==0이므로 가능

1,2,3,4 -> != 0 이므로 불가

1,2,3,4,5 ==0이므로 가능

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int main() {
	//freopen("input.txt.txt","rt",stdin);
	
	int n,k,cnt=0, sum=3,i=2;
	scanf("%d",&n);
	
	
	// 1 , 2
	// 1, 2, 3 
	//
	
	
	while(sum<=n){
		if((n-sum)%i==0){
			int add = (n-sum)/i;
			for(k=1 + add ; k< i+add ;k++){
				printf("%d + ",k);
			}
			printf("%d = %d\n",k,n);
			cnt++;
		}
		i++;
		sum+=i;
	}
	
	
	printf("%d",cnt);


}

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int main() {
	//freopen("input.txt.txt","rt",stdin);
	
	int a, b=1, cnt=0, tmp, i;
	scanf("%d",&a);
	tmp=a;
	a--;
	while(a>0){
		b++;
		a=a-b;
		if(a%b==0){
			for(i=1; i<b; i++){
				printf("%d + ", (a/b)+i);
			}
			printf("%d = %d\n", (a/b)+i, tmp);
			cnt++;
		}
	}

	printf("%d",cnt);


}

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

int a[11];
using namespace std;
int main() {
	int s, n, i,j;
	scanf("%d",&s);
	scanf("%d",&n);
	
	for(i=0;i <n;i++){
		int val , idx;
		scanf("%d",&val);
		
		bool isin = false;
		
		for(j=0; j<s; j++){
			if(a[j]==val){
				isin = true;
				idx = j;
				break;
			}
		}
		
		// cache hit // 있으면 그 숫자만 앞으 로 
		if(isin){
			for(j=idx; j>=1; j--){
				a[j] = a[j-1];
				a[j-1] = val;
			}
		} 
		else{
		// cache miss // 없으면 다 뒤로 밀고 맨앞에
			for(j=s-1; j>=1; j--){
				a[j] = a[j-1];
			}
			a[0] = val;
		}
		
		
		for(j=0; j<s; j++){
			printf("%d ", a[j]);
		}
		printf("\n");
		
		
		
	}
	
	
	
	return 0;
}

----

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

int c[11];
using namespace std;
int main() {
	int s,n,a, i,j,pos;
	scanf("%d %d", &s, &n);
	
	for(i=1; i<=n; i++){
		scanf("%d", &a);
		pos=-1;
		for(j=0;j<s;j++)if(c[j]==a) pos=j;
		if(pos==-1){
			for(j=s-1; j>=1; j--) c[j]=c[j-1];
		}
		else{
			for(j=pos; j>=1; j--) c[j]=c[j-1];
		}
		c[0] = a;
	}
	for(i=0; i<s; i++){
		printf("%d ", c[i]);
	}
	
}