JArchive 프로그래밍 일기

숫자의 표현 문제링크 

리뷰 

입력이 15일 때, 15 하나 자체도 표현 방법으로 친다. 

그래서 answer 는 1로 초기화한다. 

15를 2로 나눴을때의 몫 부터 연속된 수를 더해본다. 

15를 2로 나눴을때의 몫은 7이다. 

7부터 더해보고,

6부터 더해보고, 

5부터 더해보고, 

.... 

1부터 더해보고. 

15/2 부터 1까지 누적 덧셈을 시도한다. 더하다가 n과 똑같아지면 카운팅한다. 

맞았습니다 코드 

#include <string>
#include <vector>
using namespace std;

int solution(int n) {
  int answer = 1;
  int start = n/2;

  for(int i = start; i > 0; i--){ // start 부터 1 까지.
    int sum = i, j = i+1; // 합을 저장할 sum, 더해줄 숫자 j
    while(sum <= n){
      sum += (j++);
      if(sum == n) {answer++; }
    }
  }
  return answer;
}

JadenCase 문자열 만들기 문제링크

리뷰 

문자열에는 숫자도 공백문자도 포함되어 있다.

문자열을 하나씩 순회해서 문자마다 알파벳이 맞는지 확인하는 isalpha() 함수를 썼다. 이건 불필요한 작업이었다. 

공백이든 숫자든 toupper() 와 tolower() 에 영향을 받지 않고 에러도 안낸다..

공백과 연속된 문자를 대문자로 바꾸고, 나머지는 전부 lower 처리 하면 된다. 

맞았습니다 코드1

#include <string>
#include <vector>
using namespace std;

string solution(string s) {

  string answer = "";
  string space_delimiter = " ";
  int pos = 1;

  while(pos != string::npos){
    pos = s.find(space_delimiter);
    string w = s.substr(0, pos);

    if (isalpha(w[0])) { w[0] = toupper(w[0]); };
    for(int i = 1; i < w.size(); i++){
      if (isalpha(w[i])) { w[i] = tolower(w[i]); };
    }
    answer += (w + " ");
    s.erase(0, pos + space_delimiter.length());
  }
  answer = answer.substr(0, answer.size()-1);
  return answer;
}

더 짧은 맞았습니다 코드2

#include <string>
#include <vector>
using namespace std;

string solution(string s) {
  string answer = "";

  answer += toupper(s[0]);
  for(int i = 1; i < s.size(); i++){
    if(s[i-1] == ' '){ // 공백 뒤에 대문자
      answer += toupper(s[i]);
    }else{
      answer += tolower(s[i]);
    }
  }

  return answer;
}

문제 링크 

리뷰 

1이 나타나는 곳에서 1이 끝날때 까지의 길이를 세서 정사각형인지 확인하는 방법을 썼다. 

근데 테스트 케이스 몇개가 안되서 다른 방법이 필요했다. 

맞았습니다 코드 

#include <bits/stdc++.h>
using namespace std;

int solution(vector<vector<int>> board)
{
  int answer = board[0][0];
  int h = board.size();
  int w = board[0].size();

  for(int i = 1; i < h; i++){
    for(int j = 1; j < w; j++){
      if(board[i][j] == 1){
        // 오른쪽, 아래, 대각선의 최소값을 구하고, 1을 더한다.
        board[i][j] = 1 + min({board[i-1][j-1], board[i][j-1], board[i-1][j]});
        answer = max(board[i][j], answer);
      }
    }
  }
  return answer * answer;
}

지도 자동 구축 문제 링크 

리뷰 

점 개수가 늘어나는 규칙보다는 전체 개수의 규칙을 셌다. 

0단계에서 한 변의 점 개수는 2개다. 

1단계에서 한 변의 점 개수는 3개다. 

2단계 에서는 5개, 3 단계에서는 9개가 된다. 

사각형의 전체 점 개수는 한 변의 점 개수의 제곱이다. 

2, 3, 5, 9  ==>  2의 0승 1승 2승 만큼 증가한다.  여기서 DP를 이용해 짰다. 

맞았습니다 코드 

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int n;
ll D[10];
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  D[0] = 2, D[1] = 3;
  ll addnum = 1;
  for(int i =2; i <= n; i++){
    addnum *= 2;
    D[i] = D[i-1] + addnum;
  }
  cout << D[n] * D[n];
  return 0;
}

제출기록

우물 안 개구리 문제 링크 

리뷰 

힘을 저장하는 배열 power 과, 최고라고 생각한다/안한다 를 저장하는 iambest 배열을 따로 만들었다. 

처음에는 모두 다 '나는 최고'라고 생각하도록 iambest를 1로 초기화 했다. 

친분관계를 순회하면서 자신보다 힘쎈 사람인지 power 배열 값으로 비교한다. 

힘이 같거나 힘이 약하면 iambest 값을 0 으로 바꾼다. 

마지막에 iambest 가 1인 사람만 카운팅 해서 답을 낸다. 

코드를 짜고 나니깐 이차원 배열로 해도 상관없을 것 같다는 생각이 들었다. 

맞았습니다 코드 

#include <bits/stdc++.h>
using namespace std;

int n, m, a, b, answer;

 int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m;

  vector<bool> iambest(n+1, 1);
  vector<int> power(n+1, 0);

  for(int i = 1; i <= n; i++) cin >> power[i];

  while(m--){
    cin >> a >> b;
    if(power[a] < power[b]){
      iambest[a] = 0;
    }else if(power[a] > power[b]){
      iambest[b] = 0;
    }else{
      iambest[a] = 0;
      iambest[b] = 0;
    }
  }
  // 아직 1인 사람(최고라고 생각) 카운팅
   for(int i = 1; i <= n; i++) if (iambest[i] > 0) answer++;
   
  cout << answer;
  return 0;
}

제출 기록 

H-클린알파 문제 링크

리뷰

바이러스가 1초, 2초, 3초 ... 1초 간격으로 들어온다. 

바이러스가 들어올 때는 증가율을 신경쓰지않고 개수 그대로 더해줘야 한다. 

이미 있었던 바이러스에만 증가율 p를 곱해주면 된다. 

맞았습니다 코드 

#include <bits/stdc++.h>
#define ll long long
#define MOD 1000000007
using namespace std;

ll p, n, total_cnt, num;
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> p >> n;
  while(n--){
    cin >> num; // 바이러스 개수 입력받기
    total_cnt = (total_cnt * p + num) % MOD;
  }
  cout << total_cnt;
  return 0;
}

제출기록 

문제 링크 

리뷰 

처음에 이중 for문으로 하다가 시간초과나서 틀렸다. 

left 부터 right까지의 인덱스 찾기

일차원 배열일 때, 행 하나씩 0,1,2,3,4,5 의 연속적인 값의 인덱스를 갖는다. 

해당 인덱스의 값 찾기

n = 4 일 때 , 1, 2, 3, 4 값을 가지는 칸은 이중 for문으로 이차원 배열을 순회할 때의 (i, j) 좌표를 떠올리자. 

i와 j를 비교했을 때, 큰 값을 '값'으로 가진다. 

맞았습니다 코드 

#include <string>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

vector<int> answer;
vector<int> v;
vector<int> solution(int n, long long left, long long right) {

  for(ll i = left; i <= right; i++){
    answer.push_back(1+ max(i / n, i % n));
  }
  return answer;
}