int main() 
{
  int c;
  int k;
  int n;
  vector<vector<int>> matrix;
  
  vector<int> ans;
  cin >> c;

  for(int i=0; i<=14; i++) //15 x 15 matrix 생성
  {
    vector<int> v;
    
    for(int j=0; j<=14; j++)
    {
      if(i == 0)
        v.push_back(j);
      else if(j==0)
        v.push_back(0);
      else 
        v.push_back(v[j-1] + matrix[i-1][j]); // 옆집과 아랫집의 사람수의 합
    }
    matrix.push_back(v);
  }

  for(int i=0; i<c; i++) // 정답들 추가
  {
    cin >> k;
    cin >> n;

    ans.push_back(matrix[k][n]);

    
  }

  for(int i=0;i<c; i++)
  {
    cout << ans[i] <<'\n';
  }

  return 0;
}

IDEA : O(n³) Brute force로 가능한 ip 분할을 모두 탐색함

s 길이가 3이하 혹은 13이상이면 ""리턴

1단계 1,2,3 분할
2단계 1,2,3 분할
3단계 1,2,3 분할
4단계 3단계에 맞게 ip설정

다음 단계로 넘어갈 때 이전 단계에서 분할한 ip가 맞는지 확인 후 넘어감

class Solution {
public:
    vector<string> restoreIpAddresses(string s) 
    {
        vector<string> ans;
        
        if(s.size() > 12 || s.size() < 4)
            return ans;
        
        int remain; // 한 단계 분할 후 사용할 수 있는 남은 글자수를 저장
        
        string a_ip,b_ip,c_ip,d_ip;
        for(int a=1; a<=3; a++)
        {
            a_ip = s.substr(0,a);
            remain = s.size() - a_ip.size();
            
            if(remain >= 3 && is_able(a_ip))
            {
                for(int b=1; b<=3; b++)
                {
                    b_ip = s.substr(a,b);
                    remain = s.size() - a_ip.size() - b_ip.size();
                
                    if(remain >= 2 && is_able(b_ip))
                    {
                        for(int c=1; c< remain; c++)
                        {
                            c_ip = s.substr(a+b,c);
                            d_ip = s.substr(a+b+c, s.size() - a+b+c);
                            
                            if(is_able(c_ip) && is_able(d_ip))
                                 ans.push_back(a_ip+"."+b_ip+"."+c_ip+"."+d_ip);
                        }
                    }
            
                }
            }
        }
                    

        return ans;                        
    }
    
    bool is_able(string a)
    {
        if(a.size() >= 2 && a[0] == '0') //2자리순데 처음이 0으로 시작하면 안됨
            return false;
        else if(stoi(a) > 255) //ip 허용 범위 초과하면 안됨
            return false;
        return true;
    }
};

long long int로 풀어 보려 했는데, 10^10000이 long long int 마저 초과해버림

그래서 string으로 풂

IDEA
'0' == 48 
a, b 둘 중 작은 글자 수만큼 반복 

Ex :  a = 99, b = 1123면 

3 + 9 -> 12 
2를 넣고 
1을 올림 

2 + 9 + 1 = 12 
2를 넣고 
1을 올림 

1 올린 거와 '1123'의 1을 더해 
2를 넣음 

0 올린 거와 '1123'의 1을 더해 
1을 넣음

int main() 
{
  string a , b; 
  string tmp;
  string ans;

  int up = 0; //올림 수
  int one;
  int sum;
  cin >> a >> b;


  //a는 짧은 거로 b는 긴 거로
  if(a.size() > b.size())
  {
    tmp = a;
    a = b;
    b = tmp;
  }
  //a, b 길이 
  int a_s = a.size();
  int b_s = b.size();

  for(int i=0; i<b.size(); i++)
  {
    if(i < a_s) //a 길이만큼은 a와 b의 자리수를 합
      sum = a[a_s-1-i] - 48 + b[b_s-1-i] - 48 + up;
  
    else //이후부터는 b의 자리수만 
      sum = b[b_s-1-i] - 48 + up;
      
    one = sum % 10;
    up = sum / 10;
    ans.insert(0,to_string(one)); //a b 합의 일의 자리수를 앞에 추가
  }

  if(up == 1) //마지막에 올림 수 가 있을 경우 앞에 추가
    ans.insert(0,to_string(up));

  cout << ans;
 
  return 0;
}

14 단어의 Case를 구분 짓고 "turu"인 부분만 몇 번 반복했는지에 따라 출력을 다르게 함

int main() 
{
  int n;
  cin >> n;
  string tu = "tu";

  int k = (n-1) / 14;

  if(n % 14 == 1 || n % 14 == 13)
    cout << "baby";
  else if(n % 14 == 2 || n % 14 == 0)
    cout << "sukhwan";
  else if(n % 14 == 3 || n % 14 == 7 || n % 14 == 11)
  {
    if(k < 3)
    {
      for(int i=0; i<k+2; i++)
        tu += "ru";
      cout << tu;
    }
    else
    {
      tu +="+ru*";
      cout << tu << k+2;
    }
  }
  else if(n % 14 == 4 || n % 14 == 8 || n % 14 == 12)
  {
    if(k < 4)
    {
      for(int i=0; i<k+1; i++)
        tu += "ru";
      cout << tu;
    }
    else
    {
      tu +="+ru*";
      cout << tu << k+1;
    }
  }
  else if(n % 14 == 5)
    cout << "very";
  else if(n % 14 == 6)
    cout << "cute";
  else if(n % 14 == 9)
    cout << "in";
  else if(n % 14 == 10)
    cout << "bed";


  return 0;
}

O(n²)로 a가 커질 때마다 확인하는 식으로 짰는데, 너무 길어져 버리면 Time Limit이 되어버림

class Solution {
public:
    int repeatedStringMatch(string a, string b) 
    {
        int count = 1;
        string a_plus = a;
        
        if(b.size() > 100)
            return -1;
        
        for(int i=0; i<b.size(); i++)
        {
                
            
            if(a_plus.size() >= b.size())
                for(int k = 0; k<= a_plus.size() - b.size(); k++)
                {
                    string sub = a_plus.substr(k,b.size());    
                    
                    if(sub.compare(b) == 0)
                        return count;
                }

                
            
            a_plus += a;
            count++;
            

        }
        
        return -1;
    }
};

처음에 카이사르 암호-> 문자인걸 문자 -> 카이사르 암호 로 풀어버림,,

int main(void)
{
  string kai;

  cin >> kai;

  for(int i=0; i<kai.size(); i++)
  {
    if(kai[i] <= 'C')
      kai[i] += 23;
    else 
      kai[i] -= 3;
  }
  
  cout << kai;

  return 0;
}

규칙을 잘 보면 6번부터 탈출이 불가능함.

5까지는 처음 open 과 반대 수로 010101 반복해서 출력하면 됨.

int main(void)
{
  int N;
  int open;
  
  cin >> N;
  cin >> open;

   if(N >= 6)
   {
      cout << "Love is open door";
      return 0;
   }
   
  for(int i=0; i<N-1; i++)
  {
    
    if(i%2 == 0 && open == 0)
        cout << 1 << '\n'; 
    
    else if(i%2 == 1 && open == 0)
        cout << 0 << '\n';

    if(i%2 == 0 && open == 1)
        cout << 0 << '\n'; 
    
    else if(i%2 == 1 && open == 1)
        cout << 1 << '\n';


  }

  return 0;
}

## 메모리 초과로 실패

## tree를 삭제하는 식으로 다시 작성해야 할 듯 하다.

IDEA

이진트리로 하루가 지날 때마다, 확률의 수가 2배로 늘어남에 따라 
전날 확률과 현재의 확률을 누적했다.

둘째 날 가능한 경우의 수가 2개이고
셋째 날 가능한 경우의 수는 2²개
n-1 째날 가능한 경우는 2ⁿ 개이다. 

int main(void)
{
  int n;
  int now;
  int idx = 0;
  double sum = 0;
  vector<double> p(4);
  vector<vector<double>> tree;

  cin >> n >> now;
  cin >> p[0] >> p[1] >> p[2] >> p[3];

  for(int i=0; i<n; i++)
  {
    vector<double> v;
    sum = 0;
    if(now == 0 && i==0) //첫날 좋은 날일 경우
    {
      v.push_back(p[0]);
      v.push_back(p[1]);
    }
    else if(now == 1 && i==0) //첫날 나쁜 날일 경우
    {
      v.push_back(p[2]);
      v.push_back(p[3]);
    }

    else //이후 날들
    {
      for(int k=0; k<pow(2, i+1); k++) // 이전 날의 확률을 참고해 곱한다.
      {
        v.push_back(tree[i-1][idx] * p[k%4]);

        if(k%2 == 1)
        {
          sum += tree[i-1][idx] * p[k%4];
          idx++;
        }

        
      }

    }
    idx = 0;
    
    tree.push_back(v);

  }

  cout << (1-sum) * 1000<< '\n' << sum * 1000;
  return 0;
}

문제 잘못 이해해서 시간이 두 배로 걸림 하하하

n = 1은 1로 기본값으로 두고

n = 2는 n=1에서 1개의 1이 있다는 뜻으로
11이 된다.

n = 3는 n=2 에서 2개의 1이 있다는 뜻으로 
21이 된다.

n = 4는 n=3 에서 1개의 2가 있고, 1개의 1이 있다는 뜻으로
1211이 된다.

"n = 5는 1231이 되겠네"

가 아니라

1개의 1이 있고, 1개의 2가 있고, 2개의 1이 있다 이므로

111221 이 되어야함

MAIN IDEA

k번째와 k+1 번째가 다르면 
카운트된 숫자와 k번째 숫자를 ans 에 더한다.

class Solution {
public:
    string countAndSay(int n) 
    {
        string ans;
        
        int count = 0;
        
        
        if(n == 1) return "1";
        else if(n == 2) return "11";

        ans = "11"; 

        for(int i=2; i<n; i++)
        {
            string tmp;
            //아래에서 정산이라함은 MAIN IDEA를 의미한다.
            for(int k=0; k<ans.size(); k++)
            {
                count++; //탐색 글자가 다음 글자와 같으면 count 증가
                
                if(k<ans.size()-1 && ans[k] != ans[k+1])
                {
                    tmp += to_string(count) + ans[k];
                    count = 0;
               // 탐색 글자가 다음 글자와 다르면 끊고 정산
                    
                }
                else if(k==ans.size()-1 && ans[k-1] == ans[k])
                {
                    tmp += to_string(count) + ans[k];
                    count = 0;
                    
                }
                // 마지막 탐색 글자가 이전 글자와 같으면 정산
                else if(k==ans.size()-1 && ans[k-1] != ans[k])
                {
                    tmp += to_string(1) + ans[k];
                    count = 0;
                   
                }
                // 마지막 탐색 글자가 이전 글자와 다르면 마지막 글자만 따로 정산
            }
            
            ans = tmp;
            
        }
        
        return ans;
    }
};

1. 시작이 5가 아니면 무조건 false 임
2. 시작이 5라면 이후
5$인 손님은 pass
10$인 손님은 5$를 주고
20$인 손님은 15$를 줘야됨

IDEA 5$,10$ 카운트를 각각 만들자
5$인 손님이 오면  -> 5카운트 증가

10인 손님이 오면
    이때 5카운트가 0이라면 false 리턴
   10카운트 증가 후 5카운트 감소

20인 손님이 오면
    10$ , 5$ 1개 씩 주면 됨
    5$ 3개를 줘도됨 
위 아래 순서 중요함 잘 생각해봐야함

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) 
    {
        int f_count = 0; // 5$ 개수
        int t_count = 0; // 10$ 개수
        
        if(bills[0] != 5) return false; // 2. 내용
        
        for(int i=0; i<bills.size(); i++)
        {
            if(bills[i] == 5)
                f_count++;
            
            else if(bills[i] == 10)
            {
                if(f_count == 0)
                    return false;
                t_count++;
                f_count--;
            }
            else if(bills[i] == 20)
            {    
                if(f_count > 0 && t_count > 0) //5$랑 10$으로 거스름
                {
                    f_count--;
                    t_count--;
                }
                else if(f_count >= 3) // 5$ 3개로 거스름
                    f_count -= 3;
                else 
                    return false;
            }
            cout<< f_count << "  " << t_count << " \n";   
        }
        return true;
    }
};

각 row 별로 순서대로 글자를 채우고 마지막에 하나로 합쳤다.

row 가 1인 경우도 제대로 작동할 줄 알았는데, 두 번째 줄로 들어가 버려 오답처리가 됐다.

class Solution {
public:
    string convert(string s, int numRows) 
    {
        vector<string> zig(numRows);
        int n = 1;
        int direct = 1;
        string ans;
        
        
        if(numRows == 1)
            return s;
        
        zig[0].push_back(s[0]);
        
        for(int i=1; i<s.size(); i++)
        {
            
            
            zig[n].push_back(s[i]);
            
            
            if( 0 < n && n < numRows - 1)
            {
                n += direct;
            }
            else
            {
                direct *= -1;
                n += direct;
            }
                
        }
        
        for(int k=0; k<numRows; k++)
        {
            ans += zig[k];
        }
        return ans;
    }
};

중간에 a 가 나와도 l_count를 다시 0으로 초기화시켜줘야 된다는 걸 놓침

class Solution {
public:
    bool checkRecord(string s) 
    {
        int a_count = 0;
        int l_count = 0;
        
        for(int i=0;i<s.size(); i++)
        {
            if(s[i] == 'L')
                l_count++;
            
            else 
            {
                if(s[i] == 'A')
                    a_count++;
                l_count = 0;
            }
            
            if(l_count == 3 || a_count >= 2)
                return false;
        }
        return true;
        
    }
};

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

실수로 Z -> A 인 부분을 무시하고 Z +=1 시켜버림

int main(void)
{
  int n;
  vector<string> ibm;
  string s;
  cin >> n;
  for(int i=0; i<n; i++)
  {
    cin >> s;

    for(int k=0; k<s.size(); k++)
    {
      if(s[k] != 'Z')
        s[k] +=1;
      else 
        s[k] = 'A';
    }  

    ibm.push_back(s);
  }

  for(int i=0; i<ibm.size(); i++)
  {
    cout <<"String #"<<i+1<<'\n'<<ibm[i];
    if(i<ibm.size())
      cout <<"\n"<<"\n"; 
  }

  return 0;
}

직관대로 풀었다.

string compare에서 살짝 헤맸다.

class Solution {
public:
    bool backspaceCompare(string s, string t) 
    {
        string ss;
        string tt;
        
        for(int i=0; i<s.size(); i++)
        {
            if(s[i] != '#')
                ss.push_back(s[i]);
            else if(ss.size()>0 &&(s[i] == '#'))
                ss.pop_back();  
        }
       
        for(int i=0; i<t.size(); i++)
        {
            if(t[i] != '#')
                tt.push_back(t[i]);
            else if(tt.size()>0 &&(t[i] == '#'))
                tt.pop_back();
            
        }
        return ss.compare(tt) == 0;
    }
    
    
};

브루트 포스 O(n³) 말고는 방법이 잘 생각나지 않는다.

투 포인터로 접근하는 문제는 아닌 듯하다.

bool is_Prime(int n);

int solution(vector<int> nums) 
{
    int answer = 0;
    
    for(int i=0; i<nums.size()-2; i++)
        for(int j=i+1; j<nums.size()-1; j++)  
            for(int k=j+1; k<nums.size(); k++)
                if(is_Prime(nums[i] + nums[j] + nums[k]))
                    answer++;
    return answer;
}

bool is_Prime(int n)
{
    for(int i=2; i<=sqrt(n); i++)
        if(n%i == 0)
            return false;
    
    return true;
    
}

생각 후 코딩을 연습해야 하는데 자꾸 쉽다고 바로 코드 작성하는 이상한 버릇이 생겨버림,,

조심하도록 하자...

int main(void)
{
  string word; //입력 단어
  char ans; //정답 출력
  
  vector<int> map(26); //letter map
  int max = 0;
  int flag = 0; // 최대값이 2개 이상 곂치는 경우 flag를 올림
  cin >> word; 

  for(int i=0; i<word.size(); i++)
  {
    if('A'<=word[i]&&word[i]<='Z') //대문자 일 때
    {  
      map[word[i]-65]++; //해당글자에 해당하는 map 증가
      if(max < map[word[i]-65]) //max 값이 새로 갱신 될 경우 
      {
        max = map[word[i]-65]; //max 값 갱신
        flag = 0; // flag를 내리고
        ans = word[i]; // 해당 글자를 정답글자로
      }
      else if(max == map[word[i]-65]) 
        flag = 1; //최대값을 가지는 단어가 여러개인 경우
    }
    
    else  //소문자 일 때
    {  
      map[word[i]-97]++;
      if(max < map[word[i]-97])
      {
        max = map[word[i]-97];
        flag = 0;
        ans = word[i]-32;
      }
      else if(max == map[word[i]-97])
        flag = 1; 
    }
  }
  if(flag == 1) // 최대값이 중복인 경우
    cout << '?';
  else // 아닌 경우
    cout << ans;



 
  return 0;
}

IDEA

1. 크기 26 int 배열(map)을 만들고

2. 단어 길이만큼 탐색

   2-1 해당 단어에 map의 값이 1 이상이면, 이미 있었다는 뜻이므로, 그룹 단어가 아님

      2-1-1 단, 한 글자 이전에 같은 글자가 있는 경우는 제외 

      2-1-2 그룹단어가 아니면 flag를 올림

   2-2 map에 해당 글자가 있으면 1을 증가시킴

실수 ,,, 하나의 단어를 검사하고 map이랑 flag를 초기화하는 걸 놓침

int main(void)
{
    string word; 
    int n;
    int count = 0;
    int flag = 0;
    
    cin >> n;
    
    for(int i=0; i<n; i++)
    {
        cin >> word;
        vector<int> map(26);
        flag = 0;
        
        if(word.size() == 1) // 1글자일 경우
        {
            count++;
            continue;
        }
        
        for(int k=1; k<word.size(); k++) //2글자 이상일 경우
        {
            map[word[k-1]-97] = 1;
            if((word[k-1] != word[k])&&(map[word[k]-97] > 0)) //그룹단어가 아닌 경우
                flag = 1;
            
        }
        
        if(flag == 0)
            count++;
    }
    
    cout << count;
    
    return 0;
}

#include <iostream>
#include <vector>
#include <string>

using namespace std;


int main(void)
{
  int n;
  int flag = 0;
  char c;
  string name;
  
  cin >> n;
  
  vector<int> map(26);

  for(int i=0; i<n; i++)
  {
    cin >> name;
    map[name[0]-97]++;
  }

  for(int i=0;i<26;i++)
  {
    if(map[i] >= 5)
    {
      c = 'a'+i;
      cout << c;
      flag = 1;
    }

  }

  if(flag == 0)
    cout << "PREDAJA";

  return 0;
}

#include <iostream>
#include <vector>
#include <string>

using namespace std;


int main(void)
{
  int time = 0;
  string num;
  cin >> num;

  

  for(int i=0;i<num.size();i++)
  {
      if('A'<= num[i] && num[i] <= 'C')
        time += 3;
      else if('D'<= num[i] && num[i] <= 'F')
        time += 4;
      else if('G'<= num[i] && num[i] <= 'I')
        time += 5;
      else if('J'<= num[i] && num[i] <= 'L')
        time += 6;       
      else if('M'<= num[i] && num[i] <= 'O')
        time += 7;
      else if('P'<= num[i] && num[i] <= 'S')
        time += 8;
      else if('T'<= num[i] && num[i] <= 'V')
        time += 9;
      else if('W'<= num[i] && num[i] <= 'Z')
        time += 10;        
  }

  cout << time;
  return 0;
}

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int score(string q);

int main(void)
{

  int n;
  vector<int> s;

  string quiz;
  cin >> n;
  for(int i=0;i<n;i++)
  {
    cin >> quiz;
    s.push_back(score(quiz));
  }

  for(int i=0;i<n;i++)
    cout << s[i]<<'\n';

  return 0;
}


int score(string q)
{
  int acc_score = 0;
  int fin_score = 0;

  for(int i=0;i<q.size();i++)
  {
  
  acc_score++;
    
    if(q[i] == 'O')
      fin_score += acc_score;
    else 
        acc_score = 0;
        
  }
  return fin_score;
}