프로그래밍

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

[난이도] Gold4
[유형] 구현

[풀이]
터널 통과전 각 자동차에 대해 자신보다 앞에 가고 있는 자동차를 적절한 자료구조에 기록해놓고
터널 통과후 앞에 이전에 있던 차가 없으면 그 차는 추월을 한것이다.
string 자체로 기록하기 위해 map,set 등을 이용하였는데 index로 변환하여 풀면
메모리 및 시간을 줄일 수 있다.

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2002.cpp

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
using namespace std;
string a[1001];
int main(){
    ios_base::sync_with_stdio();
    cin.tie();
    map<string,vector<string>> start;
    map<string,set<string>> end;
    int N;
    cin>>N;
    for(int i=N-1;i>=0;i--) cin>>a[i];
    for(int i=0;i<N-1;i++)
        for(int j=i+1;j<N;j++) start[a[i]].push_back(a[j]);
    
    for(int i=N-1;i>=0;i--) cin>>a[i];
    for(int i=0;i<N-1;i++)
        for(int j=i+1;j<N;j++) end[a[i]].insert(a[j]);
    
    int ans = 0;
    for(auto k : start){
        string n = k.first;
        for(auto e : k.second){
            if(end[n].find(e) == end[n].end()) {
                ans++;
                break;
            }
        }
    }
    cout << ans;
}

https://codeforces.com/contest/1367/problem/A

[난이도] Div.3
[유형] 구현

[풀이]
맨 앞, 맨 뒷 글자는 무조건 출력해주고
가운데 글자들은 같은 글자가 두번씩 나오므로 한번씩만 출력되도록 하면 된다.

#include <string>
#include <iostream>
using namespace std;
int tc;
int main(){
    cin >> tc;
    while(tc--){
        string s;
        cin >> s;
        cout << s[0];
        for(int i=1;i<s.size()-1;i+=2) cout << s[i];
        cout << s.back();
        puts("");
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round650-Div.3/A.cpp

https://codeforces.com/contest/1409/problem/C

[난이도] Div.3
[유형] 구현

[풀이]
a2−a1=a3−a2=…=an−an−1=k 를 등차 k가 가장 적게하면서 만족할수록
max(a1,a2,…,an)의 값은 작아지게 된다. k=1부터 체크하면서 조건을 만족하는
수열을 만들 수 있는지 확인해보자

#include <cstdio>
using namespace std;
int n,x,y,tc;
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d%d%d",&n,&x,&y);
        int s,e,j;
        for(int i=1;;i++){
            int cnt=1;
            j=i;
            if((y-x)%i) continue;
            s=x,e=y;
            cnt+=(y-x)/i;
            if(cnt > n) continue;
            if(cnt == n) break;
            s -= ((x-1)/i)*i;
            if((x-1)/i+cnt>=n) {
                cnt+=(x-1)/i;
                s+=(cnt-n)*i;
                break;
            }
            cnt+=(x-1)/i;
            e+=(n-cnt)*i;
            break;
        }
        for(int i=s;i<=e;i+=j) printf("%d ",i);
        puts("");
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round667-Div.3/C.cpp

https://codeforces.com/contest/1409

[난이도] Div.3
[유형] 구현

[풀이]
axb가 작아지려면 a와 b의 차이가 크게 날수록 작아진다.
n을 a에서 먼저 뺄수 있을 만큼 빼주고 b에서 뺄 수 있을 만큼 빼준값과
n을 b에서 먼저 뺄수 있을 만큼 빼주고 a에서 뺄 수 있을 만큼 빼준값을
비교해서 더 작은 값을 정답으로 하면 된다.

#include <cstdio>
#include <algorithm>
using namespace std;
using ll = long long;
int tc; 
ll a,b,x,y,n,ret;
ll sol(){
    ll ans,tn;
    if(a-x>=n){
        ans = (a-n)*b;
    }else{
        tn = n-(a-x);
        ans = x*max(y,b-tn);
    }
    return ans;
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d%d%d%d%d",&a,&b,&x,&y,&n);
        ret = sol();
        swap(a,b);
        swap(x,y);
        ret = min(ret,sol());
        printf("%lld\n",ret);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round667-Div.3/B.cpp

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

[난이도] Gold4
[유형] 구현

[풀이]
그냥 구현하면 시간초과가 난다. (1000000*700*2=14억) 의 연산이 필요
=> 최적화가 필요하다.
1. 0,1,2 성장중에서 가장 비중을 많이 차지하는 성장치(a)를 구함
2. 모든 날에 그 a만큼 성장한다고 가정하고 그 모든날에 a만큼 더해줌.
3. 실제로 N개의 입력을 재순회 사면서 성장치가 a인 경우는 스킵하고 a가 아닌 경우에는
그 값으로 수정하는 보정값을 더해준다.
(이 과정으로 시간을 줄이기 때문에 가장 비중을 많이 차지하는 성장치 a를 골랐다. 그 비중만큼 스킵이 가능하기 때문에. 적어도 1/3만큼은 스킵이 가능하다.)
4. 왼쪽열과 행의 최종 값이 업데이트 되었으므로 M*M 배열을 채워준다.

※ 가장 많은 가중치를 구하지 않고 무조건 0을 스킵하는 방식으로 해도 AC를 받을 수 있다고 한다.
※ 누적합 개념을 이용하면 O(N) 의 시간으로 해결이 가능하다. (이게 정해인듯함. 위의 풀이는 O((2*M)/3*N))

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N,M,map[700][700],t[1400],a[1000000][3],mi;
pair<int,int> cnt[3];
int main(){
    scanf("%d%d",&N,&M);
    
    for(int i=0;i<M;i++){
        for(int j=0;j<3;j++){
            int v;
            scanf("%d",&v);
            cnt[j].second=j;
            cnt[j].first+=v;
            a[i][j]=v;
        }
    }
    sort(cnt,cnt+3);
    mi = cnt[2].second;
    for(int i=0;i<2*N;i++) t[i]=mi*M;

    for(int i=0;i<M;i++){
        int k=0;
        for(int j=0;j<3;j++){
            int s=k,e=k+a[i][j];
            if(j!=mi){
               for(int l=s;l<e;l++){
                   t[l]+=(j-mi);
               } 
            }
            k=e;
        }
    }
    int j=0;
    for(int i=N-1;i>=0;i--) map[i][0] = t[j++];
    for(int i=1;i<N;i++) map[0][i] = t[j++];

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(i&&j) map[i][j] = max(map[i-1][j-1],max(map[i-1][j],map[i][j-1]));
            printf("%d ",map[i][j]+1);
        }
        puts("");
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/10836.cpp

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

[난이도] Gold4
[유형] 재귀

[풀이]
2차원 배열을 선언한 뒤, 재귀함수로 큰 삼각형부터 그려준다.
공백은 ' '으로 표시해야하며, 더이상 *가 없다면 다음 라인으로 넘어가야
오답을 피할 수 있다.

#include <algorithm>
#include <cstdio>
using namespace std;
bool map[2500][2500];
int N,eg[11];
void prt(int n,int sy,int sx){ 
    if(n==0) return;
    int h=eg[n],w=(h-1)*2+1,d=1,ey,ex=sx+w-1;
    if(n%2==0) {
        ey=sy+h-1;
    }else{
        d=-1;
        ey=sy-h+1;
    }
    for(int i=sx;i<=ex;i++) map[sy][i] = 1;
    int k=1;
    for(int y=sy+d;y!=ey+d;y+=d,k++){
        map[y][sx+k] = map[y][ex-k] = 1;
    }
    prt(n-1,(sy+ey)/2,sx+h/2+1);
}
int main(){
    scanf("%d",&N);
    eg[1]=1;
    for(int i=2;i<=N;i++) eg[i]=eg[i-1]*2+1;
    int k=0,d=1;
    if(N%2) prt(N,eg[N]-1,0);
    else {
        k=eg[N]-1,d=-1;
        prt(N,0,0);
    }

    for(int i=0;i<eg[N];i++){
        for(int j=0;j<eg[N]+k;j++) printf("%c",map[i][j] ? '*':' ');  
        k+=d;
        if(i<eg[N]-1) puts("");
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/10993.cpp

https://programmers.co.kr/learn/courses/30/lessons/60058

[풀이] 재귀,구현,Stack

문제에 써있는 대로 구현하면 된다.

1. 균형잡힌 괄호 문자열 찾기 int getBalance(string& s)

  여는 괄호와 닫는 괄호의 갯수가 같아지는 순간의 index를 반환

2. 올바른 문자열 체크 bool isRight(string& s)

  stack을 이용하였다. 여는 괄호의 경우 무조건 push, 닫는 괄호인 경우에

  stack이 비어있으면 올바른 괄호 문자열이 아니므로 false 리턴

위의 두 함수를 이용해서 재귀적으로 solution 함수를 채워주면 된다.

#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
string p = "()";
int getBalance(string& s) {
	int ret = 0;
	int l=0, r=0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '(') l++;
		else r++;
		if (l == r) {
			ret = i+1;
			break;
		}
	}
	return ret;
}

bool isRight(string& s) {
	stack<int> st;

	for (int i = 0; i < s.size(); i++) {
		char c = s[i];
		if (c == '(') {
			st.push(c);
		}
		else {
			if (st.empty()) {
				return false;
			}
			else {
				st.pop();
			}
		}

	}
	return true;
}
string rev(string& s) {
	string ret = "";
	for (int i = 1;i<s.size()-1;i++) {
		ret.push_back(s[i] == ')' ? '(' : ')');
	}
	return ret;
}

string solution(string p) {
	
	if (p == "") return p;
	string ret;

	int sz = getBalance(p);
	string w = p.substr(0, sz);
	string u = p.substr(sz, p.size() - sz);

	string k = solution(u);
	if (isRight(w)) {
		ret = w + k;
	}
	else {
		ret = "("+k+")";
		ret += rev(w);
	}
	return ret;
}

https://github.com/has2/Algorithm/blob/master/programmers/level2/%EA%B4%84%ED%98%B8%20%EB%B3%80%ED%99%98.cpp