nose딩

계차수열만 알면 풀 수 있는 문제;; 

* 계차수열 => 수1 ? 기억도 안나 ㅎ

an = 1 3 9 19 33 ... => 층 맨 첫 원소

bn = 2 6 10 14

  => 2 + 4(n-1) = 4n-2

an = a1+ 2*(N*(N-1))-((N-1)*2)

    = 1 + 2*(N*(N-1))-((N-1)*2)

an = 1 7 17 31 ... => 층 맨 마지막 원소

bn = 6 10 14 ...

  => 6 + 4(n-1) = 4n+2

an = a1 +  2*(N*(N-1)) + ((N-1)*2) = 1 + 2*(N*(N-1)) + ((N-1)*2)

=> n이 층

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;

public class Solution {
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T;
		T=Integer.parseInt(br.readLine());
		
		StringBuffer sb = new StringBuffer();
		StringTokenizer st;
		for(int test_case = 1; test_case <= T; test_case++)
		{
			int N = Integer.parseInt(br.readLine());
			st = new StringTokenizer(br.readLine()," ");
			int[] arr = new int[N];
 			String result = "Yes";
			for(int i=0; i<N; i++) {
				arr[Integer.parseInt(st.nextToken())-1]+=1;
			}
			Arrays.sort(arr);
			if(arr[0]!=arr[N-1]) result="No";
			
			sb.append("#"+test_case+" "+result).append('\n');
		}
		System.out.print(sb);
	}
}

첨에는 arraylist로 풀었는데 시간 초과 떠서

그냥 int형 배열로 푸니 풀렸다,,^^,,

import java.util.Scanner;

public class Solution {
	public static void main(String[] args){
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner(System.in);
		
		int T;
		T=Integer.parseInt(sc.nextLine());
		
		for(int test_case = 1; test_case <= T; test_case++)
		{
			int N = Integer.parseInt(sc.nextLine());
			
			int[] arr = new int[N];
			
			for(int i=0; i<N; i++) {
				arr[i]=Integer.parseInt(sc.nextLine());
			}
			
			int count = 0;
			
			for(int i=1; i<N; i++) {
				if(arr[i]==0) continue;
				int day=arr[i]-1; //주기
				count ++;
				for(int j=i+1; j<N; j++) { //돌면서 저 주기 체크~
					if((arr[j]-1)%day==0) arr[j]=0; //방문 표시
				}
			}
			System.out.println("#"+test_case+" "+count);
		}
	}
}

나는 몽총이 ~

나머지 연산으로 저리 샥 샥 ,,

방문도 걍 0 으로 표시 하면 되는데 ~~~~~~~ 아아악

import java.util.Scanner;
import java.util.StringTokenizer;

public class Solution {
	static int[] arr;
	static int max;
	static int maxIndex;
	static long result;
	static int N;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner(System.in);
		int T;
		T=Integer.parseInt(sc.nextLine());
		StringTokenizer st;
		String answer="";
		for(int test_case = 1; test_case <= T; test_case++)
		{
			result = 0;
			
			N= Integer.parseInt(sc.nextLine());
			
			arr = new int[N];
			
			st = new StringTokenizer(sc.nextLine()," ");
			for(int i =0; i<N; i++) {
				arr[i]=Integer.parseInt(st.nextToken());
			}
			buy(0); 
			answer += "#"+test_case+" "+result+'\n';
		}
		System.out.println(answer);
	}
	
	static void buy(int start) { 
		if(start >= N) return;
		max = Integer.MIN_VALUE;
		maxIndex = 0;
		
		for(int i=start; i<N; i++) {
			if(arr[i]>= max) {
				max = arr[i];
				maxIndex = Math.max(i,maxIndex);
			}		
		}
		if(maxIndex==N) return;
		
		if(maxIndex-start>0) {
			for(int i=start;i<maxIndex; i++) {
				result+= max-arr[i];
			}
		}
		buy(maxIndex+1);
	}
}

테케 3개가 틀려서 뭐지했는데

결과값의 자료형이 int인게 문제였움

long 으로 해주기 하아아아아 허무해~

import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;
class Solution {
    public int[] solution(String[] id_list, String[] report, int k) {
        HashMap<String, HashSet<String>> reportPeople = new HashMap<>(); //신고 당한 사람, 신고한사람
        HashMap<String, Integer> reportCount = new HashMap<>(); //사람 별 신고 횟수
        int[] answer = new int[id_list.length];
        //map초기화
        for (int i = 0; i < id_list.length; i++) {
	        reportPeople.put(id_list[i], new HashSet<String>());
	        reportCount.put(id_list[i], 0);
        }
        StringTokenizer st;
        for(int i =0;i<report.length; i++){
            st = new StringTokenizer(report[i]," ");
            String user1 = st.nextToken();
            String user2 = st.nextToken();
            reportPeople.get(user2).add(user1);
        }
       
        for (String key : reportCount.keySet()) { 
            HashSet<String> set = reportPeople.get(key); 
                if(set.size() >= k) { 
                    for (String setKey : set) {
                        reportCount.put(setKey, reportCount.get(setKey)+1);
                    } 
                } 
        } 
        
        for (int i = 0; i < id_list.length; i++) {
            answer[i] = reportCount.get(id_list[i]); 
        }

        
        return answer;
    }
}

아 똥멍청인가 아ㅓㄹ ㅏ어아ㅓㅏ

1단계가 더 못풀겠네;; ^_ㅜ

import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Collections;
import java.util.HashMap;
import java.util.Collections;
class Solution {
    public int[] solution(String[] genres, int[] plays) {
        ArrayList<Integer> result = new ArrayList<>();
        
        Song[] songs = new Song[genres.length];
        HashMap<String, ArrayList<Song>> genreSongs = new HashMap<>();   //장르별 노래
        HashMap<String, Integer> genrePlays = new HashMap<>();//장르별 재생 횟수
        for(int i=0; i<genres.length; i++){
            songs[i]=new Song(i,genres[i],plays[i]);
            if(genrePlays.containsKey(genres[i])){
                genrePlays.put(genres[i],genrePlays.get(genres[i])+plays[i]);
            }else{
                genrePlays.put(genres[i],plays[i]);
            }
            if(genreSongs.containsKey(genres[i])){
                ArrayList<Song> al = genreSongs.get(genres[i]);
                al.add(songs[i]);
                genreSongs.put(genres[i],al);
            }else{
                ArrayList<Song> al = new ArrayList<>();
                al.add(songs[i]);
                genreSongs.put(genres[i],al);
            }
        }
        
        //장르 횟수 합 기준으로 정렬
        ArrayList<String> keySetList = new ArrayList<>(genrePlays.keySet());
        Collections.sort(keySetList,new Comparator<String>(){
            @Override
            public int compare(String a, String b){
                return genrePlays.get(b)-genrePlays.get(a);
            }
        });
                         
        for(String s : keySetList){ //같은 장르
           //같은 장르내에서 많이 재생된 노래 ~ 
           ArrayList<Song> al = genreSongs.get(s);
           Collections.sort(al, new Comparator<Song>(){
              @Override
               public int compare(Song s1, Song s2){
                   int temp = s2.plays-s1.plays;
                   if(temp==0){
                       temp = s1.id-s2.id;
                   }
                   return temp;
               }
           });
            //최대 두개
            int count = 1;
            for(Song so : al){
                if(count>2) break;
                result.add(so.id);
                count++;
            }
        }
        
        int answer[] = new int[result.size()];
        
        for(int i=0; i<result.size(); i++){
            answer[i]=result.get(i);
        }
        
        return answer;
    }
}
class Song{
    int id;
    String genre;
    int plays;
    public Song(int id,String genre,int plays){
        this.id=id;
        this.genre=genre;
        this.plays=plays;
    }
}

너무 더러워 더러워 흑흑

해시맵 정렬은,, keySet 정렬 이용하기 ,,, 메모 

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        int whM = brown+yellow;
        int whP = ((whM-yellow)/2)+2;
        
        for(int w=1;w<=brown; w++){
            for(int h=1; h<=w; h++){
                if(w+h==whP && w*h==whM){
                    answer[0]=w;
                    answer[1]=h;
                    break;
                }
            }
        }
        
        return answer;
    }
}

wh = brown+yellow

yellow = (w-2)*)(h-2) -> w+h = (wh+4-yellow)/2

돌면서 저 식 두개 만족하면 종료 ,,

class Solution {
    static int[][] dp;
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        int mod = 1000000007;
        dp=new int[n+1][m+1];
        //물 찬 구역 표시하기
        for(int i=0; i<puddles.length; i++){
            dp[puddles[i][1]][puddles[i][0]]=-1;
        }
        dp[1][1]=1;
        for(int i=1; i<=n; i++){
           for(int j=1; j<=m; j++){
               if(dp[i][j]==-1){
                   continue;
               }
               if(dp[i-1][j]!=-1) dp[i][j] += dp[i-1][j]%mod;
               if(dp[i][j-1]!=-1) dp[i][j] += dp[i][j-1]%mod;
           }
        }
        return (dp[n][m])%mod;
    }
}

아니 왜 안될까 하며 뭐지 했는데 내가 문제 잘못읽었다 ;;;; ;;; 어이없어 ㅠ

최단경로 개수구하는 거였는데 그냥 최단경로일때 숫자 구하는줄 알았다;;;ㅠ; 오늘의 멍청비용 ㅠ